本文共 1357 字，大约阅读时间需要 4 分钟。
链接：
代码：
#include #include #include #include #include #include #include #include using namespace std;#define N 1000005#define oo 0x3fffffffstruct node{ int a, b, next; long long p;}s1[N], s[N];int n, m, head[N];long long dis[N];bool vis[N];void Add(int a, int b, long long p, int k){ s1[k].a=a; s1[k].b=b; s1[k].p=p; s1[k].next=head[a]; head[a]=k;}long long spfa(){ queue Q; Q.push(1); vis[1]=true; for(int i=1; i<=n; i++) dis[i]=oo; dis[1]=0; while(Q.size()) { int i = Q.front(); Q.pop(); vis[i] = false; for(int j=head[i]; j != 0; j = s1[j].next) { int a = s1[j].a, b = s1[j].b; int p = s1[j].p; if(dis[a]+p < dis[b]) { dis[b] = dis[a] + p; if(vis[b] == false) { Q.push(b); vis[b] = true; } } } } long long sum=0; for(int i=1; i<=n; i++) sum += dis[i]; return sum;}int main(){ int t; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); int i; memset(head, 0, sizeof(head)); memset(s, 0, sizeof(s)); memset(s1, 0, sizeof(s1)); for(i=1; i<=m; i++) { scanf("%d%d%I64d", &s[i].a, &s[i].b, &s[i].p); Add(s[i].a, s[i].b, s[i].p, i); } long long ans = spfa(); memset(head, 0, sizeof(head)); for(i=1; i<=m; i++) Add(s[i].b, s[i].a, s[i].p, i); ans += spfa(); printf("%I64d\n", ans); } return 0;}
转载于:https://www.cnblogs.com/YY56/p/4744394.html