旅游规划

青旅半醒 2022-04-06 05:27 300阅读 0赞

## 题目描述 ##

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

## 输入描述 ##

输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

## 输出描述 ##

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

## 输入样例 ##

4 5 0 3
    0 1 1 20
    1 3 2 30
    0 3 4 10
    0 2 2 20
    2 3 1 20

## 输出样例 ##

3 40

## 提示 ##

最短路径

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #define inf 0x3fffffff
    
    int G[510][510];
    int vis[510]={0};
    int cost[510][510];
    int d[510];
    int c[510];
    
    int s,n;
    
    void Dijkstra(int s)
    {
    	int i,j,v;
    	/*for (i=0;i<510;i++)
    	{
    		c[i] = d[i] = inf;
    	}*/
    	
    	c[s] = 0;
    	d[s] = 0;
    	vis[s] =  1;
    	for (i=0;i<n;i++)
    	{
    		int u = -1;
    		int MIN = inf;
    		for (j=0;j<n;j++)
    		{
    			if (vis[j]==0 && d[j] < MIN)
    			{
    				MIN = d[j];
    				u = j;
    			}
    		}
    		if (u==-1) return;
    		vis[u] = 1;
    		
    		for (v=0;v<n;v++)
    		{
    			if (vis[v]==0 && G[u][v]!=inf )
    			{
    				if (d[u]+G[u][v]<d[v])
    				{
    					d[v] = d[u] + G[u][v];
    					c[v] = c[u] + cost[u][v];
    				}
    				else if (d[u]+G[u][v]==d[v] && c[u]+cost[u][v]<c[v])
    				{
    					c[v] = c[u] + cost[u][v];
    				}
    			}	
    		}		
    	}
    }
    
    int main()
    {
    	int m,j,k,i,T,x,y,len,price,e;
    	scanf("%d%d%d%d",&n,&m,&s,&e);
    	for (i=0;i<n;i++)
    	{
    		for (j=0;j<n;j++)
    		{
    			G[i][j] = G[j][i] = inf;
    			cost[i][j] = cost[j][i] = inf;
    		}
    	}
    	while (m--)
    	{
    		scanf("%d%d%d%d",&x,&y,&len,&price);
    		G[x][y] = G[y][x] = len;
    		cost[x][y] = cost[y][x] = price;
    	}
    	for (i=0;i<n;i++)
    	{
    		d[i] = G[s][i];
    		c[i] = cost[s][i];
    	}
    	Dijkstra(s);
    	printf("%d %d\n",d[e],c[e]);
    	
    	return 0;
    }