PAT(Advanced)1111 Online Map Dijkstra最短路 C++实现

PAT(Advanced)1111 Online Map Dijkstra最短路 C++实现

PAT(Advanced)1111 Online Map Dijkstra最短路 C++实现

相关内容

PAT(Advanced)1003 Emergency (Dijkstra最短路) （邻接矩阵）C++实现
DijkstraSSSP（单源最短路径求解）（迪克斯特拉算法堆优化）（Java实现）（邻接矩阵）（优先级队列）（堆优化）
Dijkstra最短路（迪克斯特拉算法）（C++实现）（邻接矩阵）
PAT(Advanced)1087 All Roads Lead to Rome Dijkstra最短路 C++实现

题目链接

1111 Online Map

题目大意

给定一张有向图，求解距离最短路和时间最短路，对于距离最短路，若存在多条距离最短路，则选取时间较短的，对于时间最短路，若存在多条时间最短的路径，输出节点最少的

算法思路

根据题意，采用Dijkstra最短路算法，设置dist数组维护距离最短路径距离代价，设置times数组维护时间最短路径时间代价，设置dijkstraSSSP数组维护距离最短路径各顶点的直接前驱索引，设置dijkstraSSFTP数组维护时间最短路径各顶点的直接前驱索引

void dijkstra(int source) {//初始化vector<bool> tag;tag.resize(vextexNumber);dist.resize(vextexNumber);times.resize(vextexNumber);dijkstraSSSP.resize(vextexNumber);dijkstraSSFTP.resize(vextexNumber);nodeNumber.resize(vextexNumber);for (int i = 0; i < vextexNumber; i++) {tag[i] = false;dist[i] = INF;times[i] = INF;dijkstraSSSP[i] = 0;dijkstraSSFTP[i] = 0;nodeNumber[i] = 1;}dist[source] = 0;times[source] = 0;dijkstraSSSP[source] = source;dijkstraSSFTP[source] = source;// 优先级队列priority_queue<Node> pq;pq.push((Node) {source, 0});while (!pq.empty()) {int top = pq.top().order;pq.pop();if (tag[top]) {continue;}tag[top] = true;for (int i = 0; i < vextexNumber; i++) {if (dist[i] >= dist[top] + matrix[top][i].length) {if (dist[i] == dist[top] + matrix[top][i].length) {if (times[i] > times[top] + matrix[top][i].time) {// 若存在多条距离最短路径，选取时间较少者dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i]});}} else {// 若存在更短距离最小路径dist[i] = dist[top] + matrix[top][i].length;dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i]});}}if (times[i] >= times[top] + matrix[top][i].time) {if (times[i] == times[top] + matrix[top][i].time) {if (nodeNumber[i] > nodeNumber[top] + 1) {// 若存在多条时间最短路径，选取节点较少者nodeNumber[i] = nodeNumber[top] + 1;// 经过节点数较少更新为其新的前驱结点节点数加一dijkstraSSFTP[i] = top;pq.push((Node) {i, dist[i]});}} else {// 若存在更小时间最短路nodeNumber[i] = nodeNumber[top] + 1;times[i] = times[top] + matrix[top][i].time;dijkstraSSFTP[i] = top;pq.push((Node) {i, dist[i]});}}}}
}

AC代码

/*
author : eclipse
email  : eclipsecs@qq.com
time   : Sat Jun 27 10:43:02 2020
*/
#include <bits/stdc++.h>
using namespace std;struct Edge {int length;int time;
};struct Node {int order;int dist;bool operator < (const Node& x) const {return dist > x.dist;}
};const int INF = 0x3f3f3f3f;
const int MAX_SIZE = 512;
vector<int> dist;
vector<int> times;
vector<vector<Edge> > matrix;
vector<int> dijkstraSSSP;   // dijkstra single source shortest path
vector<int> dijkstraSSFTP;  // dijkstra single source fastest time path
vector<int> distanceSequence;
vector<int> timeSequence;
vector<int> nodeNumber;
int vextexNumber;void dijkstra(int source) {vector<bool> tag;tag.resize(vextexNumber);dist.resize(vextexNumber);times.resize(vextexNumber);dijkstraSSSP.resize(vextexNumber);dijkstraSSFTP.resize(vextexNumber);nodeNumber.resize(vextexNumber);for (int i = 0; i < vextexNumber; i++) {tag[i] = false;dist[i] = INF;times[i] = INF;dijkstraSSSP[i] = 0;dijkstraSSFTP[i] = 0;nodeNumber[i] = 1;}dist[source] = 0;times[source] = 0;dijkstraSSSP[source] = source;dijkstraSSFTP[source] = source;priority_queue<Node> pq;pq.push((Node) {source, 0});while (!pq.empty()) {int top = pq.top().order;pq.pop();if (tag[top]) {continue;}tag[top] = true;for (int i = 0; i < vextexNumber; i++) {if (dist[i] >= dist[top] + matrix[top][i].length) {if (dist[i] == dist[top] + matrix[top][i].length) {if (times[i] > times[top] + matrix[top][i].time) {dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i]});}} else {dist[i] = dist[top] + matrix[top][i].length;dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i]});}}if (times[i] >= times[top] + matrix[top][i].time) {if (times[i] == times[top] + matrix[top][i].time) {if (nodeNumber[i] > nodeNumber[top] + 1) {nodeNumber[i] = nodeNumber[top] + 1;dijkstraSSFTP[i] = top;pq.push((Node) {i, dist[i]});}} else {nodeNumber[i] = nodeNumber[top] + 1;times[i] = times[top] + matrix[top][i].time;dijkstraSSFTP[i] = top;pq.push((Node) {i, dist[i]});}}}}
}bool samePath() {if (distanceSequence.size() != timeSequence.size()) {return false;}for (int i = 0; i < distanceSequence.size(); i++) {if (distanceSequence[i] != timeSequence[i]) {return false;}}return true;
}void print(int source, int destination) {stack<int> s;int current = destination;while (current != source) {s.push(current);current = dijkstraSSSP[current];}distanceSequence.push_back(current);while (!s.empty()) {distanceSequence.push_back(s.top());s.pop();}current = destination;while (current != source) {s.push(current);current = dijkstraSSFTP[current];}timeSequence.push_back(current);while (!s.empty()) {timeSequence.push_back(s.top());s.pop();}if (samePath()) {printf("Distance = %d; Time = %d: ", dist[destination], times[destination]);for (int i = 0; i < distanceSequence.size(); i++) {if (i == 0) {printf("%d", distanceSequence[i]);} else {printf(" -> %d", distanceSequence[i]);}}} else {printf("Distance = %d: ", dist[destination]);for (int i = 0; i < distanceSequence.size(); i++) {if (i == 0) {printf("%d", distanceSequence[i]);} else {printf(" -> %d", distanceSequence[i]);}}printf("\nTime = %d: ", times[destination]);for (int i = 0; i < timeSequence.size(); i++) {if (i == 0) {printf("%d", timeSequence[i]);} else {printf(" -> %d", timeSequence[i]);}}}
}int main(int argc, char const *argv[]) {int N, M;scanf("%d%d", &N, &M);vextexNumber = N;matrix.resize(vextexNumber);for (int i = 0; i < vextexNumber; i++) {matrix[i].resize(vextexNumber);for (int j = 0; j < vextexNumber; j++) {matrix[i][j].length = INF;matrix[i][j].time = INF;}}for (int i = 0; i < M; i++) {int V1, V2, oneWay, length, time;scanf("%d%d%d%d%d", &V1, &V2, &oneWay, &length, &time);matrix[V1][V2].length = length;matrix[V1][V2].time = time;if (!oneWay) {matrix[V2][V1].length = length;matrix[V2][V1].time = time;}}int source, destination;scanf("%d%d", &source, &destination);dijkstra(source);print(source, destination);return 0;
}

样例输入1

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5

样例输出1

Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5

样例输入1

7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5

样例输出2

Distance = 3; Time = 4: 3 -> 2 -> 5

鸣谢

PAT

最后

• 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！

PAT(Advanced)1111 Online Map Dijkstra最短路 C++实现

PAT(Advanced)1111 Online Map Dijkstra最短路 C++实现

相关内容

PAT(Advanced)1003 Emergency (Dijkstra最短路) （邻接矩阵）C++实现
DijkstraSSSP（单源最短路径求解）（迪克斯特拉算法堆优化）（Java实现）（邻接矩阵）（优先级队列）（堆优化）
Dijkstra最短路（迪克斯特拉算法）（C++实现）（邻接矩阵）
PAT(Advanced)1087 All Roads Lead to Rome Dijkstra最短路 C++实现

题目链接

1111 Online Map

题目大意

给定一张有向图，求解距离最短路和时间最短路，对于距离最短路，若存在多条距离最短路，则选取时间较短的，对于时间最短路，若存在多条时间最短的路径，输出节点最少的

算法思路

根据题意，采用Dijkstra最短路算法，设置dist数组维护距离最短路径距离代价，设置times数组维护时间最短路径时间代价，设置dijkstraSSSP数组维护距离最短路径各顶点的直接前驱索引，设置dijkstraSSFTP数组维护时间最短路径各顶点的直接前驱索引

void dijkstra(int source) {//初始化vector<bool> tag;tag.resize(vextexNumber);dist.resize(vextexNumber);times.resize(vextexNumber);dijkstraSSSP.resize(vextexNumber);dijkstraSSFTP.resize(vextexNumber);nodeNumber.resize(vextexNumber);for (int i = 0; i < vextexNumber; i++) {tag[i] = false;dist[i] = INF;times[i] = INF;dijkstraSSSP[i] = 0;dijkstraSSFTP[i] = 0;nodeNumber[i] = 1;}dist[source] = 0;times[source] = 0;dijkstraSSSP[source] = source;dijkstraSSFTP[source] = source;// 优先级队列priority_queue<Node> pq;pq.push((Node) {source, 0});while (!pq.empty()) {int top = pq.top().order;pq.pop();if (tag[top]) {continue;}tag[top] = true;for (int i = 0; i < vextexNumber; i++) {if (dist[i] >= dist[top] + matrix[top][i].length) {if (dist[i] == dist[top] + matrix[top][i].length) {if (times[i] > times[top] + matrix[top][i].time) {// 若存在多条距离最短路径，选取时间较少者dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i]});}} else {// 若存在更短距离最小路径dist[i] = dist[top] + matrix[top][i].length;dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i]});}}if (times[i] >= times[top] + matrix[top][i].time) {if (times[i] == times[top] + matrix[top][i].time) {if (nodeNumber[i] > nodeNumber[top] + 1) {// 若存在多条时间最短路径，选取节点较少者nodeNumber[i] = nodeNumber[top] + 1;// 经过节点数较少更新为其新的前驱结点节点数加一dijkstraSSFTP[i] = top;pq.push((Node) {i, dist[i]});}} else {// 若存在更小时间最短路nodeNumber[i] = nodeNumber[top] + 1;times[i] = times[top] + matrix[top][i].time;dijkstraSSFTP[i] = top;pq.push((Node) {i, dist[i]});}}}}
}

AC代码

/*
author : eclipse
email  : eclipsecs@qq.com
time   : Sat Jun 27 10:43:02 2020
*/
#include <bits/stdc++.h>
using namespace std;struct Edge {int length;int time;
};struct Node {int order;int dist;bool operator < (const Node& x) const {return dist > x.dist;}
};const int INF = 0x3f3f3f3f;
const int MAX_SIZE = 512;
vector<int> dist;
vector<int> times;
vector<vector<Edge> > matrix;
vector<int> dijkstraSSSP;   // dijkstra single source shortest path
vector<int> dijkstraSSFTP;  // dijkstra single source fastest time path
vector<int> distanceSequence;
vector<int> timeSequence;
vector<int> nodeNumber;
int vextexNumber;void dijkstra(int source) {vector<bool> tag;tag.resize(vextexNumber);dist.resize(vextexNumber);times.resize(vextexNumber);dijkstraSSSP.resize(vextexNumber);dijkstraSSFTP.resize(vextexNumber);nodeNumber.resize(vextexNumber);for (int i = 0; i < vextexNumber; i++) {tag[i] = false;dist[i] = INF;times[i] = INF;dijkstraSSSP[i] = 0;dijkstraSSFTP[i] = 0;nodeNumber[i] = 1;}dist[source] = 0;times[source] = 0;dijkstraSSSP[source] = source;dijkstraSSFTP[source] = source;priority_queue<Node> pq;pq.push((Node) {source, 0});while (!pq.empty()) {int top = pq.top().order;pq.pop();if (tag[top]) {continue;}tag[top] = true;for (int i = 0; i < vextexNumber; i++) {if (dist[i] >= dist[top] + matrix[top][i].length) {if (dist[i] == dist[top] + matrix[top][i].length) {if (times[i] > times[top] + matrix[top][i].time) {dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i]});}} else {dist[i] = dist[top] + matrix[top][i].length;dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i]});}}if (times[i] >= times[top] + matrix[top][i].time) {if (times[i] == times[top] + matrix[top][i].time) {if (nodeNumber[i] > nodeNumber[top] + 1) {nodeNumber[i] = nodeNumber[top] + 1;dijkstraSSFTP[i] = top;pq.push((Node) {i, dist[i]});}} else {nodeNumber[i] = nodeNumber[top] + 1;times[i] = times[top] + matrix[top][i].time;dijkstraSSFTP[i] = top;pq.push((Node) {i, dist[i]});}}}}
}bool samePath() {if (distanceSequence.size() != timeSequence.size()) {return false;}for (int i = 0; i < distanceSequence.size(); i++) {if (distanceSequence[i] != timeSequence[i]) {return false;}}return true;
}void print(int source, int destination) {stack<int> s;int current = destination;while (current != source) {s.push(current);current = dijkstraSSSP[current];}distanceSequence.push_back(current);while (!s.empty()) {distanceSequence.push_back(s.top());s.pop();}current = destination;while (current != source) {s.push(current);current = dijkstraSSFTP[current];}timeSequence.push_back(current);while (!s.empty()) {timeSequence.push_back(s.top());s.pop();}if (samePath()) {printf("Distance = %d; Time = %d: ", dist[destination], times[destination]);for (int i = 0; i < distanceSequence.size(); i++) {if (i == 0) {printf("%d", distanceSequence[i]);} else {printf(" -> %d", distanceSequence[i]);}}} else {printf("Distance = %d: ", dist[destination]);for (int i = 0; i < distanceSequence.size(); i++) {if (i == 0) {printf("%d", distanceSequence[i]);} else {printf(" -> %d", distanceSequence[i]);}}printf("\nTime = %d: ", times[destination]);for (int i = 0; i < timeSequence.size(); i++) {if (i == 0) {printf("%d", timeSequence[i]);} else {printf(" -> %d", timeSequence[i]);}}}
}int main(int argc, char const *argv[]) {int N, M;scanf("%d%d", &N, &M);vextexNumber = N;matrix.resize(vextexNumber);for (int i = 0; i < vextexNumber; i++) {matrix[i].resize(vextexNumber);for (int j = 0; j < vextexNumber; j++) {matrix[i][j].length = INF;matrix[i][j].time = INF;}}for (int i = 0; i < M; i++) {int V1, V2, oneWay, length, time;scanf("%d%d%d%d%d", &V1, &V2, &oneWay, &length, &time);matrix[V1][V2].length = length;matrix[V1][V2].time = time;if (!oneWay) {matrix[V2][V1].length = length;matrix[V2][V1].time = time;}}int source, destination;scanf("%d%d", &source, &destination);dijkstra(source);print(source, destination);return 0;
}

样例输入1

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5

样例输出1

Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5

样例输入1

7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5

样例输出2

Distance = 3; Time = 4: 3 -> 2 -> 5

鸣谢

PAT

最后

• 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！