对于规模较大的题目,有的时候,普通 Dijkstra 可能因为时间复杂度太高而被卡成 TLE
此时就需要使用优先队列优化的 Dijkstra 算法来解决
对于单到多的最短路径,跑一遍 Dijkstra 可以出来,但是如果是反向的呢?
不妨转变一下思路,多到单的最短路径,不就相当于将单向图的所有边的方向 reverse 一下,反向建图之后跑一遍单到多的 Dijkstra 嘛,由此可以提出反向建图的思想
# 例题
# 例题背景
有一个邮递员要送东西,邮局在节点 1。他总共要送 n−1 样东西,其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 m 条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 n−1 样东西并且最终回到邮局最少需要的时间。
# 输入格式
第一行包括两个整数,n 和 m,表示城市的节点数量和道路数量。
第二行到第 (m+1) 行,每行三个整数,u,v,w,表示从 u 到 v 有一条通过时间为 w 的道路。
# 输出格式
输出仅一行,包含一个整数,为最少需要的时间。
# 数据范围
对于 30% 的数据,1≤n≤200.
对于 100% 的数据,1≤n≤103,1≤m≤105,1≤u,v≤n,1≤w≤104,输入保证任意两点都能互相到达。
# 解题思路
观察题目有,显然是对 1→i 和 i→1 节点的路径长度进行求和,1→i 的可以先预处理出来,但是 i→1 的没办法,只能多次 Dijkstra,而普通 Dijkstra 会被卡掉,要用优先队列优化的 Dijkstra.
c++1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| int n, m; vector<PII> gra[N]; bool st[N]; int d[N], gogo[N];
int dijstra(int from, int to) { memset(st, 0, sizeof st), memset(d, 0x3f, sizeof d);
d[from] = 0; priority_queue<PII, vector<PII>, greater<PII> > heap; heap.push({ 0, from });
while (heap.size()) { auto t = heap.top(); heap.pop();
int ver = t.second, dis = t.first; if (st[ver]) continue;
for (auto side : gra[ver]) { int j = side.first, w = side.second;
if (d[j] > d[ver] + w) { d[j] = d[ver] + w; heap.push({ d[j], j }); } } }
return d[to]; }
void solve() { cin >> n >> m; for (int i = 1, u, v, w; i <= m; i++) { cin >> u >> v >> w; gra[u].push_back({ v, w }); }
int res = 0;
memset(gogo, 0x3f, sizeof gogo); gogo[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); while (heap.size()) { auto t = heap.top(); heap.pop();
int ver = t.second, dis = t.first; if (st[ver]) continue; for (auto side : gra[ver]) { int j = side.first, diss = side.second;
if (gogo[j] > gogo[ver] + diss) { gogo[j] = gogo[ver] + diss; heap.push({gogo[j], j}); } } }
for (int i = 1; i <= n; i++) res = res + gogo[i] + dijstra(i, 1);
cout << res << endl; }
|
# 针对给出的题的继续优化
就这样结束了?数据水让你打那么多次 Dijkstra 了吗?
- 1→i 是单到多,跑一遍 Dijkstra 能出
- i→1 是多到单,怎么解决?
反向建图!!!!
显然把这个图反过来建,就能得到 i→1 的单到多,照样从 1 点开始跑,跑出来的结果就是反着走的最小值
c++1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| int n, m; vector<PII> gra[2][N]; bool st[2][N]; int d[2][N];
void dijkstra(int idx) { d[idx][1] = 0;
priority_queue<PII, vector<PII>, greater<PII> > heap; heap.push({0, 1});
while (heap.size()) { auto t = heap.top(); heap.pop();
int ver = t.second, dis = t.first; if (st[idx][ver]) continue;
for (auto side : gra[idx][ver]) { int j = side.first, w = side.second;
if (d[idx][j] > d[idx][ver] + w) { d[idx][j] = d[idx][ver] + w; heap.push({ d[idx][j], j }); } } } }
void solve() { memset(d, 0x3f, sizeof d);
cin >> n >> m; for (int i = 1, u, v, w; i <= m; i++) { cin >> u >> v >> w; gra[0][u].push_back({v, w}), gra[1][v].push_back({u, w}); }
int res = 0;
dijkstra(0), dijkstra(1);
for (int i = 2; i <= n; i++) res = res + d[0][i] + d[1][i];
cout << res << endl; }
|