【模板】逆单源最短（反向建图） + spfa

题目要求：不仅要求单源最短路径，还要求其余点到该点的最短路径

做法：建立反图求逆单源最短路径，至于单源最短路径选择合适于题目即可

参考题目

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 typedef pair<int, int> PII;
 9 typedef pair<int, PII> PIP;
10 
11 const int N = 1000010;
12 
13 int h[N], e[N], ne[N], idx;
14 int w[N], dist[N];
15 bool st[N];
16 PIP tmp[N];
17 
18 int n, m;
19 
20 void add(int a, int b, int c)
21 {
22     e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
23 }
24 
25 void spfa()
26 {
27     memset(dist, 0x3f, sizeof dist);
28     dist[1] = 0;
29     
30     queue<int> q;
31     st[1] = true;
32     q.push(1);
33     
34     while (q.size())
35     {
36         int t = q.front();
37         q.pop();
38         st[t] = false;
39         
40         for (int i = h[t]; i != -1; i = ne[i])
41         {
42             int j = e[i];
43             
44             if (dist[j] > dist[t] + w[i])
45             {
46                 dist[j] = dist[t] + w[i];
47                 if (!st[j])
48                 {
49                     st[j] = true;
50                     q.push(j);
51                 }
52             }
53         }
54     }
55 }
56 
57 int main()
58 {
59     ios::sync_with_stdio(0);
60     cin.tie(0);
61     
62     cin >> n >> m;
63     
64     for(int i = 0; i < m; i ++ )
65     {
66         int a, b, c;
67         cin >> a >> b >> c;
68         tmp[i] = {a, {b, c}};
69     }
70     
71     memset(h, -1, sizeof h);
72     for (int i = 0; i < m; i ++ ) add(tmp[i].first, tmp[i].second.first, tmp[i].second.second);
73     
74     spfa();
75     
76     LL sum = 0;
77     for (int i = 1; i <= n; i ++ ) sum += dist[i];
78     
79     memset(h, -1, sizeof h);
80     memset(st, 0, sizeof st);
81     idx = 0;
82     
83     for (int i = 0; i < m; i ++) add(tmp[i].second.first, tmp[i].first, tmp[i].second.second);
84     
85     spfa();
86     
87     for (int i = 1; i <= n; i ++ ) sum += dist[i];
88     
89     cout << sum;
90 }