9度教程77 dijkstra算法之《单源最短路径》

九度教程77 dijkstra算法之《单源最短路径》

题目地址：http://ac.jobdu.com/problem.php?cid=1040&pid=76

//九度教程77 dijkstra算法之《单源最短路径》
//http://ac.jobdu.com/problem.php?cid=1040&pid=76
#include<stdio.h>
#define MAXN 1047483640//
typedef struct E{
	int min;
	int spend;
}E;
E mm[1001][1001],value[1001];
int main()
{
	int a,b,i,j,n,m,k,s,t,temps,tempm;
	while(~scanf("%d %d",&n,&m)&&n)
	{
		for(i=0;i<=n;i++)
		{
			flag[i]=1;//1为还没进集合，0为已进集合
			value[i].min=value[i].spend=MAXN;
			for(j=0;j<=n;j++)mm[i][j].min=mm[i][j].spend=MAXN;
		}
		for(i=0;i<m;i++)//读入m条边
		{
			scanf("%d %d",&a,&b);
			scanf("%d %d",&tempm,&temps);
			if(a==b||tempm>mm[a][b].min||tempm==mm[a][b].min&&temps>=mm[a][b].spend)continue;//考虑自环及重边。无视自环及权值较大的重边
			mm[a][b].min=tempm;mm[a][b].spend=temps;
			mm[b][a]=mm[a][b];
		}
		scanf("%d %d",&s,&t);
		flag[s]=0;//初始只包含s这个结点集合
		value[k=s].min=value[s].spend=0;//起始点的最短路min为0，花费spend为0;k初值为起始点s。
		while(k!=t)
		{
			for(i=k,j=1;j<=n;j++)
			{
				if(j==k)continue;
				if(value[j].min>value[k].min+mm[k][j].min)
				{
					value[j].min=value[k].min+mm[k][j].min;
					value[j].spend=value[k].spend+mm[k][j].spend;
				}
				else if(value[j].min==value[k].min+mm[k][j].min)
				{
					if(value[j].spend>value[k].spend+mm[k][j].spend)
						value[j].spend=value[k].spend+mm[k][j].spend;
				}
			}
			for(k=1;flag[k]==0;k++);//把k指向某一个未被包含的顶点，为了下步做准备。
			for(i=1;i<=n;i++){if(flag[i]&&(value[k].min>value[i].min||value[k].min==value[i].min&&value[k].spend>value[i].spend))k=i;}
			flag[k]=0;//设置已把k包含进来的标志
		}
		printf("%d %d\n",value[k].min,value[k].spend);
	}
	return 0;
}