HDU3873-有依赖的最短路(拓扑排序)

题目大意：

给一张图，跑最短路。但是每个点可能有前驱点集，即必须要先访问到前驱点，才能访问这个点.

题目思路:

可以发现，在这种限定条件下。我们访问节点的顺序一定是一个拓扑序.

所以思路是一边Dij一边拓扑排序.能够入列，当前仅当它的入度为0.

然后对着样例讨论一下， 竟 然 过 了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
const int maxn = 3000 + 5;
const int mod = 1e9 + 7;
int du[maxn] , bk[maxn];
ll dist[maxn];
vector<pair<int,ll>> e[maxn];
vector<int> to[maxn];
struct Node
{
    
    int id;
    ll v;
    bool operator < (const Node & a) const {
    
        return v > a.v;
    }
};
void init (int n){
    
    for (int i = 1 ; i <= n ; i++){
    
        to[i].clear();
        e[i].clear();
        dist[i] = -1;
        du[i] = bk[i] = 0;
    }
}
int main()
{
    
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--){
    
        int n , m; cin >> n >> m;
        init(n);
        for (int i = 1 ; i <= m ; i++){
    
            int x , y , z; cin >> x >> y >> z;
            e[x].push_back({
    y , z});
        }
        for (int i = 1 ; i <= n ; i++){
    
            int d; cin >> d;
            for (int j = 1 ; j <= d ; j++){
    
                int g; cin >> g;
                to[g].push_back(i);
            }
            du[i] = d;
        }
        priority_queue<Node> q;
        q.push({
    1 , 0});
        dist[1] = 0;
        while (q.size()){
    
            Node u = q.top(); q.pop();
            int id = u.id;
            ll dis = u.v;
        // cout << "现在在" << id << " 距离是 " << dis << endl;
            if (bk[id]) continue;
            bk[id] = 1;
            for (auto & v : to[id]) {
    
                du[v]--;
                if (du[v] == 0){
    
                    // 如果dist[v] == -1, 那么dis 不可能是v的最大前驱值
                    if (dist[v] != -1){
    
                        dist[v] = max(dist[v] , dis);
                        q.push({
    v , dist[v]});
                    }
                }
            }
            for (auto & g : e[id]){
    
                int v = g.first;
                ll w = g.second;
                if (dist[v] == -1 || dist[v] > dis + w){
    
                    dist[v] = dis + w;
                    if (!du[v]) q.push({
    v , dist[v]});
                }
            }
        }
        cout << dist[n] << endl;
    }
    return 0;
}