对于规模较大的题目,有的时候,普通 DijkstraDijkstra 可能因为时间复杂度太高而被卡成 TLETLE
此时就需要使用优先队列优化的 DijkstraDijkstra 算法来解决

对于单到多的最短路径,跑一遍 DijkstraDijkstra 可以出来,但是如果是反向的呢?
不妨转变一下思路,多到单的最短路径,不就相当于将单向图的所有边的方向 reversereverse 一下,反向建图之后跑一遍单到多的 DijkstraDijkstra 嘛,由此可以提出反向建图的思想

# 例题

# 例题背景

有一个邮递员要送东西,邮局在节点 11。他总共要送 n1n-1 样东西,其目的地分别是节点 22 到节点 nn。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 mm 条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 n1n-1 样东西并且最终回到邮局最少需要的时间。

# 输入格式

第一行包括两个整数,nnmm,表示城市的节点数量和道路数量。
第二行到第 (m+1)(m+1) 行,每行三个整数,u,v,wu,v,w,表示从 uuvv 有一条通过时间为 ww 的道路。

# 输出格式

输出仅一行,包含一个整数,为最少需要的时间。

# 数据范围

对于 30%30\% 的数据,1n2001 \leq n \leq 200.
对于 100%100\% 的数据,1n1031 \leq n \leq 10^31m1051 \leq m \leq 10^51u,vn1\leq u,v \leq n1w1041 \leq w \leq 10^4,输入保证任意两点都能互相到达。

# 解题思路

观察题目有,显然是对 1i1 \to ii1i \to 1 节点的路径长度进行求和,1i1 \to i 的可以先预处理出来,但是 i1i \to 1 的没办法,只能多次 DijkstraDijkstra,而普通 DijkstraDijkstra 会被卡掉,要用优先队列优化的 DijkstraDijkstra.

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

# 针对给出的题的继续优化

就这样结束了?数据水让你打那么多次 DijkstraDijkstra 了吗?

  • 1i1 \to i 是单到多,跑一遍 DijkstraDijkstra 能出
  • i1i \to 1 是多到单,怎么解决?

反向建图!!!!

显然把这个图反过来建,就能得到 i1i \to 1 的单到多,照样从 11 点开始跑,跑出来的结果就是反着走的最小值

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