SDNUOJ 1133.好人卡（SPFA 双向建边）

SDNUOJ 1133.好人卡（SPFA 双向建边）

题目链接 这道题员工需要到达所有的地方，然后再回来，求所有路程和的最小值，然后就很easy了？

正向建边没问题， 在反向建边的时候卡了一会，不太清楚怎么回来，后来想明白了，反向建一下就能回来，总的来说还是一个模板题 代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
#define maxn 1000005
#define inf 0x3f3f3f3f
int vis[maxn];
long long d[maxn];
int head[maxn];
int cnt;
int n, m;
struct node1
{int u;int v;long long w;
}e[maxn];
struct node
{int to;int next;long long w;
}a[maxn];
void init()
{for(int i = 1; i <= n; i ++){vis[i] = 0;head[i] = -1;d[i] = inf;}cnt = 0;
}
void add(int from, int to, long long w)
{a[cnt].w = w;a[cnt].to = to;a[cnt].next = head[from];head[from] = cnt ++;
}
void spfa(int s)
{queue<int>q;q.push(s);d[s] = 0;vis[s] = 1;while(! q.empty()){int h = q.front();q.pop();vis[h] = 0;for(int i = head[h]; ~ i; i = a[i].next){if(d[a[i].to] > d[h] + a[i].w){d[a[i].to] = d[h] + a[i].w;if(!vis[a[i].to]){q.push(a[i].to);vis[a[i].to] = 1;}}}}
}
int main()
{int t;scanf("%d",&t);while(t --){long long ans = 0;scanf("%d%d",&n,&m);init();for(int i = 1; i <= m; i ++){int u, v;long long w;scanf("%d%d%lld",&u,&v,&w);add(u, v, w);e[i].u = u, e[i].v = v, e[i].w = w;//add(v, u, w);}spfa(1);for(int i = 2; i <= n; i ++)ans += d[i];init();for(int i = 1; i <= m; i ++){add(e[i].v, e[i].u, e[i].w);}spfa(1);for(int i = 2; i <= n; i ++)ans += d[i];printf("%lldn",ans);}return 0;
}