PTA甲级——1030

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:

1
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:

1
2
3
4
5
6
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:

1
0 2 3 3 40

思路

​ 大致题意：给你起点、终点、一些路径的距离和代价，需要你求出距离最短的路径**(如果存在距离相同的路径则输出代价最短的，按照题目意思这种路径一定是唯一的)**具体通过哪些点 + 最短路径长度 + 最小代价。

​ 思路：首先是正常的dijsktra算法正常编写可以求出最短路径和最小代价，随后就是写一个dfs逆向搜索走过的路径就OK了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
typedef pair<int, pair<int, int>> PII;
const int N = 1010;

int n, m, s, d;
int e[N], ne[N],h[N], w1[N], w2[N], idx;
int dist1[N], dist2[N];
bool st[N];
vector<int> A;

void add(int c1, int c2, int dis, int val) {
    e[idx] = c2, ne[idx] = h[c1],w1[idx] = dis, w2[idx] = val, h[c1] = idx++;
}

PII dijkstra() {
    memset(dist1, 0x3f, sizeof dist1);
    memset(dist2, 0x3f, sizeof dist2);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist1[s] = 0;
    dist2[s] = 0;
    q.push({s, {0, 0}});
    
    while (q.size()) {
        auto t = q.top();
        q.pop();
        int k = t.first, distance = t.second.first, value = t.second.second;
        for (int i = h[k]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist1[j] > distance + w1[i]) {
                dist1[j] = distance + w1[i];
                dist2[j] = value + w2[i];
                q.push({j, {dist1[j],dist2[j]}});
            } else if (dist1[j] == distance + w1[i] && dist2[j] > value + w2[i]){
                dist2[j] = value + w2[i];
                q.push({j, {dist1[j], dist2[j]}});
            }
        }
    }
    PII t = {d, {dist1[d], dist2[d]}};
    return t;
}

void dfs(int x) {
    if (st[x]) return;
    st[x] = true;
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        // cout << j << '\n';
        // cout << dist1[j] << " " <<  w1[i] << '\n';
        // cout << dist2[j] << " " <<  w2[i] << '\n';
        if (!st[j] && dist1[x] == dist1[j] + w1[i] && dist2[x] == dist2[j] + w2[i]) {
            A.push_back(j);
            dfs(j);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m >> s >> d;
    memset(h, -1, sizeof h);
    for (int i =  1; i <= m; i++) {
        int c1, c2, dis, val;
        cin >> c1 >> c2 >> dis >> val;
        add(c1, c2, dis, val);
        add(c2, c1, dis, val);
    }

    PII t = dijkstra();
    A.push_back(d);
    dfs(d);

    for (int i = A.size() - 1; i >= 0; i--) cout << A[i] << " ";
    cout << t.second.first << " " << t.second.second;
}