2边SPFA 然后求和
#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 1000000000
#define ii __int64
using namespace std;
struct node
{
ii v;
ii val;
ii next;
}edge1[],edge2[];
ii head1[],dis1[],head2[],dis2[],vis[];
ii n,m,t,index1,index2;
void add1(ii x,ii y,ii z)
{
ii i,j;
edge1[index1].v=y;
edge1[index1].val=z;
edge1[index1].next=head1[x];
head1[x]=index1++;
}
void add2(ii x,ii y,ii z)
{
ii i,j;
edge2[index2].v=y;
edge2[index2].val=z;
edge2[index2].next=head2[x];
head2[x]=index2++;
}
void SPFA1(ii u)
{
ii i,j;
memset(vis,,sizeof(vis));
queue<ii>q;
for(i=;i<=n;i++)
dis1[i]=INF;
dis1[u]=;
vis[u]=;
q.push(u);
while(!q.empty())
{
ii v=q.front();
q.pop();
vis[v]=;
for(i=head1[v];i!=-;i=edge1[i].next)
{
ii tmp=edge1[i].v;
if(dis1[tmp]>dis1[v]+edge1[i].val)
{
dis1[tmp]=dis1[v]+edge1[i].val;
if(!vis[tmp])
{
q.push(tmp);
vis[tmp]=;
}
}
}
}
}
void SPFA2(ii u)
{
ii i,j;
memset(vis,,sizeof(vis));
queue<ii>q;
for(i=;i<=n;i++)
dis2[i]=INF;
dis2[u]=;
vis[u]=;
q.push(u);
while(!q.empty())
{
ii v=q.front();
q.pop();
vis[v]=;
for(i=head2[v];i!=-;i=edge2[i].next)
{
ii tmp=edge2[i].v;
if(dis2[tmp]>dis2[v]+edge2[i].val)
{
dis2[tmp]=dis2[v]+edge2[i].val;
if(!vis[tmp])
{
q.push(tmp);
vis[tmp]=;
}
}
}
}
}
int main()
{
ii i,j,t,m;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d%I64d",&n,&m);
index1=index2=;
memset(dis1,,sizeof(dis1));
memset(head1,-,sizeof(head1));
memset(dis2,,sizeof(dis2));
memset(head2,-,sizeof(head2));
for(i=;i<m;i++)
{
ii x,y,z;
scanf("%I64d%I64d%I64d",&x,&y,&z);
add1(x,y,z);
add2(y,x,z);
} SPFA1(); /*for(i=1;i<=n;i++)
printf("%d ",dis1[i]);
printf("\n");*/ SPFA2(); /*for(i=1;i<=n;i++)
printf("%d ",dis2[i]);printf("\n");*/ ii ans=;
for(i=;i<=n;i++)
{
ans+=dis1[i]+dis2[i];
}
printf("%I64d\n",ans);
}
}