专业个人网站_烟台开发区网站_成都黑帽seo_网站seo标题是什么意思

A4.

旅游规划问题 (☆☆)

 【题目描述】PTA(数据结构与算法题目集 7-9)

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需

要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径

都是最短的，那么需要输出最便宜的一条路径。

 【输入格式】

输入数据的第 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

二，问题分析

首先回顾一下Floyd算法
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A=[a(i,j)] n×n开始，迭代地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

Floyd算法就是求任意两点，找这两点之间是否存在一点或者多点作为中介点，能够得到两点间的最短路径。只不过这道题目我们还要考虑路径相同的情况下，要选择价值比较小的那条路径。

三，源代码

#include<bits/stdc++.h>
using namespace std;
#define MAX 100000
int main()
{
    int n,m,s,d;
    int go,to,len,cost;
    int val[505][505];
    int dist[505][505];
    while(cin>>n>>m>>s>>d){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                val[i][j]=MAX;
                dist[i][j]=MAX;
            }
        }
        for(int i=1;i<=m;i++){
            cin>>go>>to>>len>>cost;
            val[go][to]=cost;
            val[to][go]=cost;
            dist[go][to]=len;
            dist[to][go]=len;
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    if(dist[i][j]>dist[i][k]+dist[k][j]){
                        dist[i][j]=dist[i][k]+dist[k][j];
                        val[i][j]=val[i][k]+val[k][j];
                    }else if(dist[i][j]==dist[i][k]+dist[k][j]){
                        if(val[i][j]>val[i][k]+val[k][j]){
                            val[i][j]=val[i][k]+val[k][j];
                        }
                    }
                }
            }
        }
        cout<<dist[s][d]<<" "<<val[s][d]<<endl;
    }
}