POJ 3268 Silver Cow Party
POJ 1511 Invitation Cards
两道题都是有向图，求源点到各点，再从各店回到源点的最短路
一开始有点纳闷怎么求回来的最短路，后来想到只要将图的边全部反向，再求一边源点的最短路就可以了
还有一点注意的：复杂度低的图论题，数据量和数据值一般会大，所以不用快读快输的话也尽量用scanf和printf而不是cin和cout
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int maxm = 1000005;
const ll INF = 1e12;
int n,m,tot;
ll ans;
int head[2][maxm],vis[maxm];
ll d[maxm];
struct edge
{int u,v,w,nxt;
}es[2][maxm];
void add(int k,int u,int v,int w)
{es[k][tot].u=u;es[k][tot].v=v;es[k][tot].w=w;es[k][tot].nxt = head[k][u];head[k][u]=tot;
}
void spfa(int k)
{queue<int>q;memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){d[i] = INF;}d[1] = 0;q.push(1);vis[1] = 1;while(!q.empty()){int u =q.front();q.pop();vis[u] = 0;for(int i=head[k][u];i!=-1;i=es[k][i].nxt){int v = es[k][i].v,w=es[k][i].w;if(d[v]>d[u]+w){d[v] = d[u]+w;if(!vis[v]){q.push(v);vis[v] = 1;}}}}for(int i=2;i<=n;i++) ans+=d[i];
}
int main ()
{int t,u,v,w;scanf("%d",&t);while(t--){tot = 0;ans = 0;memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);add(0,u,v,w);add(1,v,u,w);tot++;}spfa(0);spfa(1);printf("%lld\n",ans);}return 0;
}