学步园

题意：n-1个ACM学生自愿者每天要从css(1站点)坐车到达剩下站点，每个人去一个站点，

到一天结束时要返回到css(1站点)，城市的交通系统是有向图，求n-1个学生车费最少。

分析：当学生去的时候相当于求点1到所有点的最短路。回来时，是求所有点到1的最短路，

数据很大肯定不能每个点求一次，建反图后就是求1到搜有点的最短路了，用dijkstra()可以解决,

数据太大，用dijkstra()+优先队列，总结果会超int，wrong了几次，，，，，，

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#define N 1000001
#define inf 0x3fffffff
using namespace std;
int n,m,vis[N];
long long sum;
struct edge
{
	struct edge *next;
	int end,w;
}*e[N],*ce[N];//ce:反图
struct node
{
	int s;
	int w;
	friend bool operator < (node a, node b) 
	{
		return a.w>b.w;  
	}
};
void addedge(int x,int y,int w)
{
	edge *p=new(edge),*q=new(edge);
	p->next=e[x];q->next=ce[y];
	p->end=y;    q->end=x;
	p->w=w;    q->w=w;
	e[x]=p;    ce[y]=q;
}
void dijkstra(struct edge **q)
{
	priority_queue<node> Q;
	int num=0;
	node cur,next;
	cur.s=1;
	cur.w=0;
	Q.push(cur);
	memset(vis,0,sizeof(vis));
	while(!Q.empty())
	{
		cur=Q.top();
		Q.pop();
		if(vis[cur.s]==1)continue;//点被标记了，就不往下进行了
		vis[cur.s]=1;
		sum+=cur.w;
		num++;
		if(num==n)break;
		for(struct edge *p=q[cur.s];p;p=p->next)
		{
			next.s=p->end;
			next.w=p->w+cur.w;
			if(vis[next.s]==0)
				Q.push(next);
		}		
	}
}
int main()
{
	int j,x,y,w,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		memset(e,NULL,sizeof(e));
		memset(ce,NULL,sizeof(ce));
		for(j=0;j<m;j++)
		{
			scanf("%d%d%d",&x,&y,&w);
			addedge(x,y,w);
		}
		sum=0;
		dijkstra(e);
		dijkstra(ce);
		printf("%lld\n",sum);		
	}
	return 0;
}