题意：学生从A站到B站花费C元，将学生每天从‘1’号站送往其它所有站，再从所有站接回到‘1’号站，问着个过程最小花费是多少。
思路：因为数据很大所以要用SPFA，因为不仅要从1点连接各个点还要从各个点返回一点，所以需要正邻接表和逆邻接表。然后正反各跑一次SPFA，值得注意的是因为数据很大，要将INF定位0xffffffff。
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<string>
#include<math.h>
#include<queue>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<cmath> #define INF 0xffffffff
#define MAX 1000005 using namespace std; int vis[MAX],a[MAX],b[MAX],k,n,m; long long dist[MAX]; struct node
{
int u,v,nextgo,nextback;
long long w;
} Map[MAX]; void Init()
{
int i,j; memset(vis,,sizeof(vis)); for(i=; i<MAX; i++)
{
a[i]=-;
b[i]=-;
dist[i]=INF*;
}
} void Add(int u,int v,int w)
{
Map[k].u=u;
Map[k].v=v;
Map[k].w=w;
Map[k].nextgo=a[u];//正向建图
Map[k].nextback=b[v];//逆向建图
a[u]=k;
b[v]=k++;
} long long gospfa()
{
long long sum=; queue<int>Q;
int start=,i;
vis[start]=;
dist[start]=;
Q.push(start); while(!Q.empty())
{
start=Q.front();
Q.pop();
vis[start]=; for(i=a[start]; i!=-; i=Map[i].nextgo)
{
int v=Map[i].v;
if(dist[v] > dist[start]+Map[i].w)
{
dist[v]=dist[start]+Map[i].w; if(!vis[v])
{
vis[v]=;
Q.push(v);
}
}
}
} for(i=; i<=n; i++)
{
sum+=dist[i];
} return sum;
} long long backspfa()
{
long long sum=; queue<int>Q;
int start=,i;
vis[start]=;
dist[start]=;
Q.push(start); while(!Q.empty())
{
start=Q.front();
Q.pop();
vis[start]=; for(i=b[start]; i!=-; i=Map[i].nextback)
{
int u=Map[i].u;
if(dist[u] > dist[start]+Map[i].w)
{
dist[u]=dist[start]+Map[i].w; if(!vis[u])
{
vis[u]=;
Q.push(u);
}
}
}
} for(i=; i<=n; i++)
{
sum+=dist[i];
} return sum;
} int main()
{
int T,i,j,u,v;
long long w,ans; scanf("%d",&T); while(T--)
{
ans=;
k=; scanf("%d%d",&n,&m); Init(); for(i=; i<=m; i++)
{
scanf("%d%d%lld",&u,&v,&w); Add(u,v,w);
} ans+=gospfa(); for(i=;i<MAX;i++)
dist[i]=INF;
memset(vis,,sizeof(vis)); ans+=backspfa(); printf("%lld\n",ans);
} return ;
}