最短路径问题

3 21 2 5 62 3 4 51 30 0 Sample Output
9 11 Source浙大计算机研究生复试上机考试-2010年 Recommend
思路：最短路径，双权值
#include<cstdio>#define MAX 999999999int dp[1111][1111];                          //表示两点间距离int dis[1111];                           //表示某点到起点距离int vis[1111];                       //来记录某点是否遍历过int used[1111];                     //某点到起点所需价钱int cost[1111][1111];                          //两点间价钱int n,m,st,ed;void init()                  //赋初值{	for(int i=1;i<=n;i++)	{		dis[i]=MAX;		vis[i]=0;		used[i]=MAX;		for(int j=1;j<=n;j++)		{		    cost[i][j]=cost[j][i]=MAX;		    dp[i][j]=dp[j][i]=MAX;		}	}}void dijkstra(){	dis[st]=0;	used[st]=0;	while(1)	{		int v=-1;		for(int i=1;i<=n;i++)		{			if(!vis[i]&&(v==-1||dis[i]<dis[v]))			    v=i;		}		if(v==-1)		   break;		vis[v]=1;		for(int i=1;i<=n;i++)		{			if(dis[i]>(dis[v]+dp[v][i]))			{			    used[i]=used[v]+cost[v][i];			    dis[i]=dis[v]+dp[v][i];		    }			else if(dis[i]==(dis[v]+dp[v][i]))			{				if(used[i]>(used[v]+cost[v][i]))				    used[i]=used[v]+cost[v][i];			}		}	}}int main(){	while(~scanf("%d%d",&n,&m)&&(m||n))	{		init();		while(m--)		{			int a,b,d,p;			scanf("%d%d%d%d",&a,&b,&d,&p);			if(dp[a][b]>d||dp[a][b]==d&&cost[a][b]>p)             //这一步很重要			{				dp[a][b]=dp[b][a]=d;				cost[a][b]=cost[b][a]=p;//先找最短路径，路径一样短，找价格最少，必须这样来写。更新，很重要。 			}		}		scanf("%d%d",&st,&ed);		dijkstra();		printf("%d %d/n",dis[ed],used[ed]);	}}
notonlysuccess   |   We have carefully selected several similar problems for you:  2066 1217 2112 1142 1548