http://acm.hdu.edu.cn/showproblem.php?pid=1535
这道题两遍spfa,第一遍sfpa之后,重新建图,所有的边逆向建边,再一次spfa就可以了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
#define maxn 1000001
using namespace std;
const int inf=; long long dis1[maxn];
long long dis2[maxn];
int e1,head[maxn],e2;
bool vis[maxn];
int cnt[maxn];
int P,Q,s,e,n;
long long w;
struct node
{
int u,v,next;
long long w;
}p[maxn],p1[maxn]; void add(int u,int v,long long w)
{
p[e1].u=u;
p[e1].v=v;
p[e1].w=w;
p[e1].next=head[u];
head[u]=e1++;
} bool spfa(int src,long long dis[])
{
queue<int>q;
memset(cnt,,sizeof(cnt));
memset(vis,false,sizeof(vis));
for(int i=; i<=n; i++) dis[i]=inf;
dis[src]=;
vis[src]=true;
q.push(src);
while(!q.empty())
{
int u=q.front(); q.pop();
vis[u]=false;
for(int i=head[u]; i!=-; i=p[i].next)
{
int vv=p[i].v;
long long ww=p[i].w;
if(dis[vv]>dis[u]+ww)
{
dis[vv]=dis[u]+ww;
if((++cnt[vv])>n) return false;
if(!vis[vv])
{
q.push(vv);
vis[vv]=true;
}
}
}
}
return true;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
e1=;
memset(head,-,sizeof(head));
scanf("%d%d",&P,&Q);
for(int i=; i<Q; i++)
{
cin>>p1[i].u>>p1[i].v>>p1[i].w;
add(p1[i].u,p1[i].v,p1[i].w);
}
n=P;
spfa(,dis1);
long long sum=;
e1=;
memset(head,-,sizeof(head));
for(int i=; i<Q; i++)
{
add(p1[i].v,p1[i].u,p1[i].w);
}
spfa(,dis2);
for(int i=; i<=n; i++)
{
sum+=(dis1[i]+dis2[i]);
}
cout<<sum<<endl;
}
return ;
}