342. 道路与航线（拓扑排序，Dijkstra综合应用）

342. 道路与航线 - AcWing题库

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到?T?个城镇，编号为?1～T。

这些城镇之间通过?R?条道路 (编号为?1?到?R) 和?P?条航线 (编号为?1?到?P) 连接。

每条道路?i?或者航线?i?连接城镇?Ai 到?Bi，花费为?Ci。

对于道路，0≤Ci≤10,000;然而航线的花费很神奇，花费?Ci 可能是负数(?10,000≤Ci≤10,000)。

道路是双向的，可以从?Ai 到?Bi，也可以从?Bi 到?Ai，花费都是?Ci。

然而航线与之不同，只可以从?Ai 到?Bi。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从?Ai 到?Bi，那么保证不可能通过一些道路和航线从?Bi 回到?Ai。

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇?S?把奶牛送到每个城镇的最便宜的方案。

输入格式

第一行包含四个整数?T,R,P,S。

接下来?R?行，每行包含三个整数（表示一个道路）Ai,Bi,Ci。

接下来?P?行，每行包含三个整数（表示一条航线）Ai,Bi,Ci。

输出格式

第?1..T 行：第?i?行输出从?S?到达城镇?i?的最小花费，如果不存在，则输出?NO PATH。

数据范围

1≤T≤25000
1≤R,P≤50000
1≤Ai,Bi,S≤T

输入样例：

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

输出样例：

NO PATH
NO PATH
5
0
-95
-100

?解析：

由于题目说：保证如果有一条航线可以从 Ai 到 Bi，那么保证不可能通过一些道路和航线从 Bi 回到 Ai。

所以图中有路线和点组成的强连通分量，可以将每个强连通分量看作是一个点，每个点之间有航线（单向边）连接，且这个由强连通分量构成的图为拓扑图。

对于单源最短路问题：

1.如果一个图的边权非负，那么就可以使用 Dijkstra 算法，时间复杂度为 mlogn.

2.如果是拓扑图，不管边权是正是负，均可按照拓扑序扫描，时间复杂度是线性的

因此，可以想到，每个强连通分量内部我们可以使用 Dijkstra 算法，强连通分量之间我们可以使用拓扑排序。

算法实现：

1.先输入所有双向道路，然后dfs出所有连通块，计算两个数组：id[] 存储每个点属于哪个连通块；vector<int>block[]存储每个连通块里有哪些点；

2.输入所有航线，同时统计出每个连通块的入度。

3.按照拓扑排序一次处理每个连通块，先将所有入读为0的连通块的编号加入队列中。

4.每次从队头取出一个连通块的编号bid

5.将改block[bid]中的所有点加入堆中，然后对堆中所有点跑Dijkstra算法。

6.每次取出堆中距离最小的点ver

7.遍历ver的所有邻点 j，如果 id[ver]=id[j]，那么如果j能被更新，则将j插入堆中；如果id[ver]！=id[j],则将id[j]这个连通块的入度减1，如果减成0了，则将其插入拓扑排序的队列中

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef pair<double, int > PDI;
typedef pair<int, int> PII;
const int N = 25000 + 5, M = 150000+5,INF=0x3f3f3f3f;
int n, mr, mp, S;
int h[N], e[M], w[M], ne[M], idx;
int din[N], id[N], d[N];
vector<int>block[N];
int vis[N];
queue<int>q;

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int ver, int cnt) {
	id[ver] = cnt;
	block[cnt].push_back(ver);
	for (int i = h[ver]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!id[j])dfs(j, cnt);
	}
}

void Dijkstra(int u) {
	priority_queue<PII, vector<PII>, greater<PII>>heap;
	for (auto i : block[u])
		heap.push({ d[i],i });
	while (!heap.empty()) {
		auto t = heap.top();
		heap.pop();
		int y = t.second;
		if (vis[y])continue;
		vis[y] = 1;
		for (int i = h[y]; i != -1; i = ne[i]) {
			int j = e[i];
			if (d[j] > d[y] + w[i]) {
				d[j] = d[y] + w[i];
				if (id[y] == id[j])
					heap.push({ d[j],j });
			}
			if (id[y] != id[j]) {
				din[id[j]]--;
				if (din[id[j]] == 0)q.push(id[j]);
			}
		}
	}
}

void topsort(int cnt) {
	for (int i = 1; i < cnt; i++) {
		if (!din[i])q.push(i);
	}
	while (!q.empty()) {
		int t = q.front();
		q.pop();
		Dijkstra(t);
	}
}

int main() {
	scanf("%d%d%d%d", &n, &mr, &mp, &S);
	memset(h, -1, sizeof h);


	for (int i = 1,a,b,c; i <= mr; i++) {
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
		add(b, a, c);
	}
	int cnt = 1;
	for (int i = 1; i <= n; i++) {
		if (!id[i]) {
			dfs(i, cnt);
			cnt++;
		}
	}

	for (int i = 1,a,b,c; i <= mp; i++) {
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
		din[id[b]]++;
	}
	memset(d, 0x3f, sizeof d);
	d[S] = 0;
	topsort(cnt);

	for (int i = 1; i <= n; i++) {
		if (d[i] > INF / 2) {
			printf("NO PATH\n");
		}
		else {
			printf("%d\n", d[i]);
		}
	}

	return 0;
}

?