Zhao70's Blog

PAT1030. Travel Plan

发表于 | 分类于

题目大意

PAT1030

给定一个图, 图中边有两类边权, 路径长度 和 花费, 选择路径长度最短的路线, 并保存. 当存在相同长度的最优解, 花费最小的解.

题目分析

按照路径长度进行边的松弛, 此时不要忘记对花费进行松弛.
当路径长度相同时, 按照花费进行松弛.

保存图中最短路径时, 记录当前结点的前一个结点. 输出答案时, 回溯即可.

代码

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
81
82
83
84
#include <iostream>
#include <stack>
using namespace std;
const int arrSize = 510;
const int INF = 9999999;
int dist[arrSize][arrSize];
int cost[arrSize][arrSize];
int path[arrSize];
int disCost[arrSize];
int disDist[arrSize];
bool isVis[arrSize];
int nVertex, nEdge, srcCity, tarCity;
void init(){
    for(int i = 0; i < nVertex; i++){
        path[i] = -1;
        disCost[i] = INF;
        disDist[i] = INF;
        isVis[i] = false;
        for(int j = 0; j < nVertex; j++){
            dist[i][j] = cost[i][j] = INF;
            if(i == j){
                dist[i][i] = cost[i][i] = 0;
            }
        }
    }
}
int main(){
    cin >> nVertex >> nEdge >> srcCity >> tarCity;
    init();
    for(int i = 0; i < nEdge; i++){
        int a, b;
        cin >> a >> b;
        cin >> dist[a][b] >> cost[a][b];
        dist[b][a] = dist[a][b];
        cost[b][a] = cost[a][b];
    }
    for(int i = 0; i < nVertex; i++){
        disDist[i] = dist[srcCity][i];
        disCost[i] = cost[srcCity][i];
    }
    isVis[srcCity] = true;
    for(int i = 0; i < nVertex - 1; ++i){
        int u;
        int minV = INF;
        for(int j = 0; j < nVertex; j++){
            if(isVis[j])
                continue;
            if(disDist[j] < minV){
                minV = disDist[j];
                u = j;
            }
        }
        isVis[u] = true;
        for(int v = 0; v < nVertex; v++){
            if(disDist[u] + dist[u][v] < disDist[v]){
                disDist[v] = disDist[u] + dist[u][v];
                disCost[v] = disCost[u] + cost[u][v];
                path[v] = u;
            }
            else if(disDist[u] + dist[u][v] == disDist[v]){
                if(disCost[u] + cost[u][v] < disCost[v]){
                    disCost[v] = disCost[u] + cost[u][v];
                    path[v] = u;
                }
            }
        }
    }
    stack<int> sav;
    int p = tarCity;
    while(p != -1){
        sav.push(p);
        p = path[p];
    }
    sav.push(srcCity);
    while(!sav.empty()){
        cout << sav.top() << " ";
        sav.pop();
    }
    cout << disDist[tarCity] << " " << disCost[tarCity];
    return 0;
}