题解 | 虫洞网络

#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int m,start,end,total;
    cin>>m>>start>>end>>total;
    if(start==end){return 0;}
    vector<vector<pair<int,int>>>graph(501+m);
    for(int i=501;i<501+m;i++){
        int ci,ni;
        cin>>ci>>ni;
        for(int j=1;j<=ni;j++){
            int sini;
            cin>>sini;
            graph[i].push_back({ci,sini});
            graph[sini].push_back({0,i});
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq;
    vector<int>dist(501+m,INT_MAX);
    vector<bool>vis(501+m,false);
    pq.push({0,start});
    dist[start]=0;
    vis[start]=true;
    while (!pq.empty()) {
    auto [d,u]=pq.top();
    pq.pop();
    if(u==end){break;}
    if(d>dist[u]){continue;}
    for(auto [w,v]:graph[u]){
        if(vis[v]){continue;}
        int new_dist = dist[u] + w;
            // 如果找到更短的路径，更新距离和前驱
        if (new_dist < dist[v]) {
            dist[v] = new_dist;
            pq.push({new_dist, v});
        }
    }
    }
    if(dist[end]>total){
        cout<<"-1";
    }else {
    cout<<dist[end];
    }
    
    return 0;
}