PAT甲级1111Online Map

Posted on | | Visitors:
Words count in article: 907 字 | Reading time ≈ 5 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856

题解

题目要求

  • 输入

    • N：取值范围是[2,500]，结点数量，索引为[0,N-1]
    • M：正整数，边的数量
    • M条边
    • 起点和终点

  • 输出

    • 最短路径

      如果最短路径不唯一，输出其中最快的那条路径

    • 最快路径

      如果最快路径不唯一，输出其中经过结点最少的那条路径

解题思路

这道题是先后做两次dijkstra+DFS，即可求解。

解法是dijkstra+DFS的题目还有：

  1. PAT甲级1087All Roads Lead to Rome
  2. PAT甲级1030Travel Plan
  3. PAT甲级1018Public Bike Management

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
// Problem: PAT Advanced 1111
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856
// Tags: 图 最短路 单源最短路 dijkstra BFS DFS

#include <iostream>
#include <vector>
using namespace std;

int n, m, start, destination;
const int INF = 99999999;
const int MAXN = 500;
bool visited[MAXN];
int dis[MAXN][MAXN];
int timee[MAXN][MAXN];
int minDis[MAXN];
int minTime[MAXN];
vector<int> disPath, timePath, tempPath, disPre[MAXN], timePre[MAXN];
int disPathMinTime = INF, timePathMinNodeCount = INF;

int calcPathTime(vector<int>& vec){
    int sum = 0;
    for (int i = vec.size() - 1; i >= 1; i--){
        sum += timee[vec[i]][vec[i - 1]];
    }
    return sum;
}

void disDFS(int v)
{
    tempPath.push_back(v);
    if (v == start){
        int pathTime = calcPathTime(tempPath);
        if (disPathMinTime > pathTime){
            disPath = tempPath;
            disPathMinTime = pathTime;
        }
        tempPath.pop_back();
        return;
    }
    for (int i = 0; i < disPre[v].size(); i++)
        disDFS(disPre[v][i]);
    tempPath.pop_back();
}

void timeDFS(int v)
{
    tempPath.push_back(v);
    if (v == start){
        if (timePathMinNodeCount > tempPath.size()){
            timePath = tempPath;
            timePathMinNodeCount = tempPath.size();
        }
        tempPath.pop_back();
        return;
    }
    for (int i = 0; i < timePre[v].size(); i++)
        timeDFS(timePre[v][i]);
    tempPath.pop_back();
}

int main()
{
    fill(dis[0], dis[0] + MAXN * MAXN, INF);
    fill(timee[0], timee[0] + MAXN * MAXN, INF);
    fill(minDis, minDis + MAXN, INF);
    fill(minTime, minTime + MAXN, INF);

    scanf("%d %d", &n, &m);
    int v1, v2, oneWay, l, t;
    for (int i = 0; i < m; i++){
        scanf("%d %d %d %d %d", &v1, &v2, &oneWay, &l, &t);
        if (oneWay == 1){
            dis[v1][v2] = l;
            timee[v1][v2] = t;
        }
        else if (oneWay == 0){
            dis[v1][v2] = dis[v2][v1] = l;
            timee[v1][v2] = timee[v2][v1] = t;
        }
    }
    scanf("%d %d", &start, &destination);

    minDis[start] = 0;
    for (int i = 0; i < n; i++){
        int u = -1, tempMin = INF;
        for (int j = 0; j < n; j++){
            if (!visited[j] && tempMin > minDis[j]){
                tempMin = minDis[j];
                u = j;
            }
        }

        if (u == -1) break;
        visited[u] = true;

        for (int v = 0; v <n; v++){
            if (!visited[v] && dis[u][v] != INF){
                if (minDis[v] > minDis[u] + dis[u][v]){
                    minDis[v] = minDis[u] + dis[u][v];
                    disPre[v].clear();
                    disPre[v].push_back(u);
                }
                else if (minDis[v] == minDis[u] + dis[u][v]){
                    disPre[v].push_back(u);
                }
            }
        }
    }
    disDFS(destination);

    fill(visited, visited + MAXN, false);

    minTime[start] = 0;
    for (int i = 0; i < n; i++){
        int u = -1, tempMin = INF;
        for (int j = 0; j < n; j++){
            if (!visited[j] && tempMin > minTime[j]){
                u = j;
                tempMin = minTime[j];
            }
        }
        if (u == -1) break;
        visited[u] = true;
        for (int v = 0; v < n; v++){
            if (!visited[v] && timee[u][v] != INF){
                if (minTime[v] > minTime[u] + timee[u][v]){
                    minTime[v] = minTime[u] + timee[u][v];
                    timePre[v].clear();
                    timePre[v].push_back(u);
                }
                else if (minTime[v] == minTime[u] + timee[u][v]){
                    timePre[v].push_back(u);
                }
            }
        }
    }
    tempPath.clear();
    timeDFS(destination);

    bool isIdentical = true;
    if (disPath.size() == timePath.size()){
        for (int i = 0; i < disPath.size(); i++){
            if (disPath[i] != timePath[i]){
                isIdentical = false;
                break;
            }
        }
    }
    else{
        isIdentical = false;
    }

    if (isIdentical){
        printf("Distance = %d; Time = %d: %d", minDis[destination], minTime[destination], start);
        for (int i = disPath.size() - 2; i >= 0; i--){
            printf(" -> %d", disPath[i]);
        }
    }
    else{
        printf("Distance = %d: %d", minDis[destination], start);
        for (int i = disPath.size() - 2; i >= 0; i--){
            printf(" -> %d", disPath[i]);
        }
        printf("\nTime = %d: %d", minTime[destination], start);
        for (int i = timePath.size() - 2; i >= 0; i--){
            printf(" -> %d", timePath[i]);
        }
    }
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!