题目大意

题目链接

有n个点(n <= 1e6), m条单向边(m <= 1e6), n - 1个人从 点1 出发,去剩余n-1个点并回到1点, 求来回的和的最小值。
其中注意权值和 小于 1e9 (这就是个坑, 一眼看去不用ll就能过, 其实不然。。。)

分析

用正的有向图跑一边, 逆的有向图跑一边, 最后求和就行了。

代码

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

#define eps 1e-8
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1e6 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

inline ll read() {
ll res = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
return f ? (~ res + 1) : res;
}

struct edge {
int u, v, w, ne;
} ed[2][M];

int vis[2][N], head[2][N], dis[2][N];
int n, m, cnt[2];

void add(int op, int u, int v, int w) {
ed[op][cnt[op]] = {u, v, w, head[op][u]};
head[op][u] = cnt[op]++;
}

void init() {
memset(vis, 0, sizeof vis);
memset(head, -1, sizeof head);
memset(dis, INF, sizeof dis);
cnt[0] = cnt[1] = 0;
}
void dijk(int op, int s) {
priority_queue<P, vector<P> , greater<P> > q;
dis[op][s] = 0;
q.push(P(0, s));
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[op][u]) continue;
vis[op][u] = 1;
for (int i = head[op][u]; ~i; i = ed[op][i].ne) {
int v = ed[op][i].v, w = ed[op][i].w;
if (dis[op][v] > dis[op][u] + w)
dis[op][v] = dis[op][u] + w, q.push(P(dis[op][v], v));
}
}
}
int main(){
int t = read();
while(t--){
n = read(), m = read();
init();
while(m--){
int u = read(), v = read(), w = read();
add(0, u, v, w), add(1, v, u, w);
}
// 0 代表原图, 1代表逆图
dijk(0, 1); dijk(1, 1);
ll ans = 0;
// 要用long long
for (int i = 1; i <= n; ++i) ans += 0ll + dis[0][i] + dis[1][i];
cout << ans << "\n";
}
return 0;
}
恰似你一低头的温柔,较弱水莲花不胜寒风的娇羞, 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践, 那么学得快, 忘得也快。