数据结构实验之图论七：驴友计划

红太狼 2022-06-04 01:28 149阅读 0赞

数据结构实验之图论七：驴友计划  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
Problem Description

做为一个资深驴友，小新有一张珍藏的自驾游线路图，图上详细的标注了全国各个城市之间的高速公路距离和公路收费情况，现在请你编写一个程序，找出一条出发地到目的地之间的最短路径，如果有多条路径最短，则输出过路费最少的一条路径。  
Input

连续T组数据输入，每组输入数据的第一行给出四个正整数N,M，s，d，其中N(2 <= N <= 500)是城市数目，城市编号从0～N-1，M是城市间高速公路的条数，s是出发地的城市编号，d是目的地的城市编号；随后M行，每行给出一条高速公路的信息，表示城市1、城市2、高速公路长度、收费额，中间以空格间隔，数字均为整数且不超过500，输入数据均保证有解。  
Output

在同一行中输出路径长度和收费总额，数据间用空格间隔。  
Example Input

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

3 40  
Hint

Author

xam

#include <stdio.h>
    
    //最短路径--floyd动态算法
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    const int MAX = 1050;
    #define INF 0x3f3f3f
    int mmp[MAX][MAX];
    int val[MAX][MAX];
    
    void floyd(int v)
    {
        int i, j, z;
        for (z = 0; z < v; z++)
        {
            for (i = 0; i < v; i++)
            {
                for (j = 0; j < v; j++)
                {
                    if (i != j)
                    {
                        //动态选择最短路径
                        if (mmp[i][j] > mmp[i][z] + mmp[z][j])
                        {
                            mmp[i][j] = mmp[i][z] + mmp[z][j];
                            val[i][j] = val[i][z] + val[z][j];
                        }
                        if (mmp[i][j] == mmp[i][z] + mmp[z][j])
                        {
                            if (val[i][j] > val[i][z] + val[z][j])
                            {
                                val[i][j] = val[i][z] + val[z][j];
                            }
                        }
                    }
                }
            }
        }
    }
    
    int main()
    {
        int t;
        cin >> t;
        while (t--)
        {
            int v, e, s, d;
            cin >> v >> e >> s >> d;
            int i, j;
            for (i = 0; i < v; i++)
            {
                for (j = 0; j < v; j++)
                {
                    if (i == j)
                        mmp[i][j] = val[i][j] = 0;
                    else
                        mmp[i][j] = val[i][j] = INF;
                }
            }
            int va, vb, len, free;
            for (i = 0; i < e; i++)
            {
                cin >> va >> vb >> len >> free;
                mmp[va][vb] = mmp[vb][va] = len;
                val[va][vb] = val[vb][va] = free;
            }
            floyd(v);
            cout << mmp[s][d] << " " << val[s][d] << endl;
        }
        return 0;
    }