题解
在最短路的基础上，有的点需要在所有前置节点都到达之后才能到达。
反映到算法上就是我们为每一个点记录一下依赖的点的个数，每松弛一个点，就把它所支持的点的记录--，只有当一个点的记录为零时，它才能入队。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int head[maxn], len;
struct edge {
int to, w, nex;
}e[maxn << 1];
void Add(int u, int v, int w) {
e[++len] = (edge){v, w, head[u]};
head[u] = len;
}
int n, m;
int dis[maxn];
bool vis[maxn];
int ind[maxn];//记录每个点还有几个前置
vector<int> ned[maxn];
struct node {
int id, dis;
bool operator <(const node& x)const {
return dis > x.dis;
}
};
void Dij(int u) {
memset(dis, 0x3f, sizeof dis);
priority_queue<node> q;
dis[u] = 0;
q.push((node){u, dis[u]});
while(!q.empty()) {
int x = q.top().id;
q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; i; i = e[i].nex) {
int v = e[i].to;
if(dis[v] > dis[x] + e[i].w) {
dis[v] = dis[x] + e[i].w;
if(!ind[v]) q.push((node){v, dis[v]});
}
}
for(int i = 0; i < ned[x].size(); i++){
int v = ned[x][i];
ind[v]--;
dis[v] = (dis[v] > dis[x] ? dis[v] : dis[x]);
if(!ind[v]) q.push((node){v, dis[v]});
}
}
}
int main() {
scanf("%d %d", &n, &m);
int u, v, w;
for(int i = 1; i <= m; i++) {
scanf("%d %d %d", &u, &v, &w);
Add(u, v, w);
}
int p;
for(int i = 1; i <= n; i++) {
scanf("%d", &ind[i]);
if(ind[i])
for(int j = 1; j <= ind[i]; j++) {
scanf("%d", &p);
ned[p].push_back(i);
}
}
Dij(1);
cout << dis[n] << endl;
return 0;
}