HDU 3790 一道单源最短路径的问题

迪杰斯特拉算法，很明显。虽然自己开始尝试使用弗洛伊德，然后飞快地T了。哈哈。

这里，记一下啊哈磊的讲解。强推啊哈磊。

这里，我怎么都没有想到，又T了一次，这次TLE卡的是 scanf.....

当场死亡，，，我还以为这么多for还要有什么优化。。。

//5 7
//2 1 10 2
//2 3 8 9
//3 1 5 5
//3 4 1 2
//1 4 3 3
//4 5 2 2
//1 5 6 3
//2 5
//HDU 3790
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=0x3f3f3f3f;
int len[1005][1005];
int cost[1005][1005];
int expense[1005];
int dis[1005];
int vis[1005]; 
int main()
{
	
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0 && m==0 ) return 0;
		
		
		
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=n;j++)
			{
				if(i==j)
				{
					cost[i][i]=0;
					len[i][j]=0;
				}
				else
				{
					cost[i][j]=maxn;
					len[i][j]=maxn;
				}
			}
		}
		for(int i=0;i<m;i++)
		{
			int a,b,d,p;
			//cin>>a>>b>>d>>p;
			scanf("%d%d%d%d",&a,&b,&d,&p);
			
			if(len[a][b]>d)
			{
				len[a][b]=d;
				len[b][a]=d;
				cost[a][b]=p;
				cost[b][a]=p;
			}
		}
		int s,t;
		scanf("%d%d",&s,&t);
		//long long costans=0;
		memset(vis,0,sizeof(vis));
		
		vis[s] = 1;
		for(int i=1;i<=n;i++)
		{
			//if(s==i) continue;
			dis[i]=len[s][i];
			expense[i]=cost[s][i];
		}
		
		for(int i=1;i<=n-1;i++)
		{
			int mind = maxn;
		//	int expense=0;
			int u=0;
			for(int j=1;j<=n;j++)
			{
				if(vis[j]==0 && mind>dis[j])
				{
					mind=dis[j];
				//	printf("mind=%d  j=%d\n",mind,j);
					u=j;
				}
			}
			vis[u]=1;
			
		//	cout<<"u:"<<u<<" mind:"<<mind<<endl;
			
			for(int j=1;j<=n;j++)//松弛 
			{
				if(vis[j]==0 && dis[j]>dis[u]+len[u][j])//>dis[u]
				{
					dis[j]=dis[u]+len[u][j];
					expense[j]=expense[u]+cost[u][j];
				 } 
				 else if(vis[j]==0 && dis[j]==dis[u]+len[u][j])
				 {
				 	if(expense[j]>expense[u]+cost[u][j])
				 	{
				 		expense[j]=expense[u]+cost[u][j];
					 }
				 }
			}
			
			if(u==t) break;
		}
		
		//cout<<dis[t]<<" "<<expense[t]<<endl;
		 printf("%d %d\n",dis[t],expense[t]);
	
	
	}
	
	
	return 0;
	
}