7-9 旅游规划（25 分) 最短路

迷南。 2022-02-27 14:20 190阅读 0赞

7-9 旅游规划 （25 分)

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

### 输入格式: ###

输入说明：输入数据的第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>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int ma[505][505],val[505][505];
    int main()
    {
    	int n,m,s,d,i,j,k,x,y,z,p;
    	memset(ma,inf,sizeof ma);
    	memset(val,inf,sizeof val);
    	scanf("%d%d%d%d",&n,&m,&s,&d);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d%d%d%d",&x,&y,&z,&p);
    		ma[x][y]=ma[y][x]=z;
    		val[x][y]=val[y][x]=p;
    	}
    	for(k=0;k<n;k++)
    	{
    		for(i=0;i<n;i++)
    		{
    			for(j=0;j<n;j++)
    			{
    				if(ma[i][j]>ma[i][k]+ma[k][j])
    				{
    					ma[i][j]=ma[i][k]+ma[k][j];
    					val[i][j]=val[i][k]+val[k][j];
    				}
    				else if(ma[i][j]==ma[i][k]+ma[k][j])
    				{
    					if(val[i][j]>val[i][k]+val[k][j])
    					val[i][j]=val[i][k]+val[k][j];
    				}
    			}
    		}
    	}
    	printf("%d %d\n",ma[s][d],val[s][d]);
    }