【PAT甲级】1030 Travel Plan

1030 Travel Plan

A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (≤500) is the number of cities (and hence the cities are numbered from 0 to N−1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:

City1 City2 Distance Cost

where the numbers are all integers no more than 500, and are separated by a space.

Output Specification:

For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

Sample Input:

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

Sample Output:

0 2 3 3 40

题意

给定一个旅游地图，每个城市之间用高速公路双向连通。

第一行输入分别给定城市数量 N NN 、高速公路数量 M MM 、起始城市 S SS 和终点城市 T TT 。

第二行给定每个城市之间的道路信息，格式如下：

城市1的编号 城市2的编号 公路长度 花费

城市编号范围是 0 ∽ N − 1 0\backsim N-10∽N−1 。

需要我们找到在最短路径下花费最少的路径，并输出最短路径中每个城市的编号、该最短路径的长度已经最小花费，保证最小花费的路径是唯一的。

思路

这道题我们可以用迪杰斯特拉算法来求最短路，这个算法大致的思想就是每次都找到图中最短的那条路径，然后更新于它相邻边的路进值，具体的讲解可以参考我之前的博客，那里有更详细的图解。

这道题可以在算法计算的过程中顺便去更新最小花费，并记录最短路径。由于题目保证最小花费的路径是唯一的，所以我们可以用一个 pre 数组来记录每个结点是从哪个结点更新过来的，遇到路径最小的或花费最小的就覆盖该结点的值，最后只需要从终点往前找，就能找到最短路径了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m, S, T;
int d[N][N], c[N][N], w[N];
int dist[N], cost[N], pre[N];
bool st[N];
void dijkstra()
{
    //初始化
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 0; j < n; j++)    //找到一条最短路径
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;
        for (int j = 0; j < n; j++)    //更新信息
        {
            if (dist[j] > dist[t] + d[t][j])
            {
                //如果找到更短的路径，将所有信息都更新
                dist[j] = dist[t] + d[t][j];
                cost[j] = cost[t] + c[t][j];
                pre[j] = t;
            }
            else if (dist[j] == dist[t] + d[t][j] && cost[j] > cost[t] + c[t][j])
            {
                //如果找到一条相同的最短路，只需更新花费更小的路径
                cost[j] = cost[t] + c[t][j];
                pre[j] = t;
            }
        }
    }
}
int main()
{
    cin >> n >> m >> S >> T;
    memset(d, 0x3f, sizeof d);
    memset(c, 0x3f, sizeof c);
    //输入公路信息
    while (m--)
    {
        int a, b, x, y;
        cin >> a >> b >> x >> y;
        d[a][b] = d[b][a] = min(d[a][b], x);
        c[a][b] = c[b][a] = min(c[a][b], y);
    }
    dijkstra(); //迪杰斯特拉算法
    //读取最短路径信息
    vector<int> path;
    for (int i = T; i != S; i = pre[i])  path.push_back(i);
    cout << S;
    for (int i = path.size() - 1; i >= 0; i--)   cout << " " << path[i];
    cout << " " << dist[T] << " " << cost[T] << endl;
    return 0;
}