构造反向图，分别求单源最短路，然后求和即可。
以下是我的代码：
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(1000007);
const int kMaxm(1000007);
const long long kInf(0x7f7f7f7f7f7f7f7f);
struct Edge
{
int v,w;
};
void SPFA(int n,int first[kMaxn],int next[kMaxm],Edge e[kMaxm],long long d[kMaxn])
{
queue<int> q;
bool inq[kMaxn];
memset(inq,false,sizeof(inq));
for(int i=1;i<=n;i++)
d[i]=kInf;
d[1]=0;
q.push(1);
inq[1]=true;
while(!q.empty())
{
int u(q.front());q.pop();
inq[u]=false;
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v),w(e[i].w);
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
if(!inq[v])
{
q.push(v);
inq[v]=true;
}
}
}
}
}
int n,m;
int cnt,first[kMaxn],next[kMaxm];Edge e[kMaxm];
int cnt2,first2[kMaxn],next2[kMaxm];Edge e2[kMaxm];
long long d[kMaxn],d2[kMaxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
cnt=cnt2=0;
memset(first,-1,sizeof(first));
memset(first2,-1,sizeof(first2));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
cnt++;
e[cnt].v=v;e[cnt].w=w;
next[cnt]=first[u];
first[u]=cnt;
cnt2++;
e2[cnt2].v=u;e2[cnt2].w=w;
next2[cnt2]=first2[v];
first2[v]=cnt2;
}
SPFA(n,first,next,e,d);
SPFA(n,first2,next2,e2,d2);
long long ans(0);
for(int i=1;i<=n;i++)
ans+=d[i]+d2[i];
cout<<ans<<endl;
}
return 0;
}
posted on 2011-07-31 09:34
lee1r 阅读(189)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论