传送门

题解

在最短路的基础上，有的点需要在所有前置节点都到达之后才能到达。

反映到算法上就是我们为每一个点记录一下依赖的点的个数，每松弛一个点，就把它所支持的点的记录--，只有当一个点的记录为零时，它才能入队。

#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;
}