【PAT甲级】1030 Travel Plan

简介: 【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;
}


目录
相关文章
|
存储 机器学习/深度学习 算法
【PAT甲级】1087 All Roads Lead to Rome
【PAT甲级】1087 All Roads Lead to Rome
70 0
【PAT甲级】1146 Topological Order
【PAT甲级】1146 Topological Order
58 0
|
存储 供应链 C++
【PAT甲级 - C++题解】1079 Total Sales of Supply Chain
【PAT甲级 - C++题解】1079 Total Sales of Supply Chain
86 0
【PAT甲级】1150 Travelling Salesman Problem
【PAT甲级】1150 Travelling Salesman Problem
48 0
|
存储
【PAT甲级】1122 Hamiltonian Cycle
【PAT甲级】1122 Hamiltonian Cycle
49 0
|
存储 供应链 C++
【PAT甲级 - C++题解】1106 Lowest Price in Supply Chain
【PAT甲级 - C++题解】1106 Lowest Price in Supply Chain
75 0
|
C++
【PAT甲级 - C++题解】1108 Finding Average
【PAT甲级 - C++题解】1108 Finding Average
67 0
【High 翻天】Higer-order Networks with Battiston Federico (8)
在本节将讨论一些观点和文化动力学模型,它们基于物理和数学文献启发、用简单规则来描述社会动态。
121 0
【High 翻天】Higer-order Networks with Battiston Federico (8)
【High 翻天】Higer-order Networks with Battiston Federico (7)
模拟人类行为的动态过程一直是许多研究的焦点,其中社会关系和交互通常被认为是一种潜在结构,是高阶方法的天然试验场。
【High 翻天】Higer-order Networks with Battiston Federico (7)
|
资源调度
【High 翻天】Higer-order Networks with Battiston Federico (5)
在给出建模之后,接下来讨论如何将传统意义下的扩散拓展到高阶系统。扩散是一个线性过程,但在许多不同的情况下都有强相关性。
【High 翻天】Higer-order Networks with Battiston Federico (5)