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

本文主要是介绍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;
}

 

这篇关于342. 道路与航线（拓扑排序，Dijkstra综合应用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---