PAT(Advanced)1030 Travel Plan Dijkstra最短路 C++实现

PAT(Advanced)甲级1030 Travel Plan Dijkstra最短路 C++实现

相关内容

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

题目链接

1030 Travel Plan

题目大意

给定无向图，求最短路径，若存在多条最短路径，则选取代价最低者

算法思路

根据题意，采用Dijkstra最短路算法，维护最短路径距离数组dist，若距离相同的路径存在多条，则考虑最小代价，设置costs数组维护最小代价

void dijkstra(int source) {vector<bool> tag;tag.resize(vextexNumber);dist.resize(vextexNumber);costs.resize(vextexNumber);dijkstraSSSP.resize(vextexNumber);for (int i = 0; i < vextexNumber; i++) {tag[i] = false;dist[i] = INF;costs[i] = INF;dijkstraSSSP[i] = 0;}dist[source] = 0;costs[source] = 0;dijkstraSSSP[source] = source;priority_queue<Node> pq;pq.push((Node) {source, 0, 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].first) {	if (dist[i] == dist[top] + matrix[top][i].first) {if (costs[i] > costs[top] + matrix[top][i].second) {// 若存在多条距离相同路径costs[i] = costs[top] + matrix[top][i].second;dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i], costs[i]});}} else {// 若存在有更短路径dist[i] = dist[top] + matrix[top][i].first;costs[i] = costs[top] + matrix[top][i].second;dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i], costs[i]});}}}}
}

AC代码

/*
author : eclipse
email  : eclipsecs@qq.com
time   : Sat Jun 27 22:51:24 2020
*/
#include <bits/stdc++.h>
using namespace std;struct Node {int order;int dist;int cost;bool operator < (const Node& x) const {return dist == x.dist ? cost > x.cost : dist > x.dist;}
};const int INF = 512;
int vextexNumber;
vector<vector<pair<int,int> > > matrix;
vector<int> dist;
vector<int> costs;
vector<int> dijkstraSSSP;void dijkstra(int source) {vector<bool> tag;tag.resize(vextexNumber);dist.resize(vextexNumber);costs.resize(vextexNumber);dijkstraSSSP.resize(vextexNumber);for (int i = 0; i < vextexNumber; i++) {tag[i] = false;dist[i] = INF;costs[i] = INF;dijkstraSSSP[i] = 0;}dist[source] = 0;costs[source] = 0;dijkstraSSSP[source] = source;priority_queue<Node> pq;pq.push((Node) {source, 0, 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].first) {if (dist[i] == dist[top] + matrix[top][i].first) {if (costs[i] > costs[top] + matrix[top][i].second) {costs[i] = costs[top] + matrix[top][i].second;dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i], costs[i]});}} else {dist[i] = dist[top] + matrix[top][i].first;costs[i] = costs[top] + matrix[top][i].second;dijkstraSSSP[i] = top;pq.push((Node) {i, dist[i], costs[i]});}}}}
}void print(int source, int destination) {stack<int> s;int current = destination;while (current != source) {s.push(current);current = dijkstraSSSP[current];}s.push(current);while (!s.empty()) {printf("%d ", s.top());s.pop();}printf("%d %d", dist[destination], costs[destination]);
}int main(int argc, char const *argv[]) {int N, M, S, D;scanf("%d%d%d%d", &N, &M, &S, &D);vextexNumber = N;matrix.resize(vextexNumber);for (int i = 0; i < matrix.size(); i++) {matrix[i].resize(vextexNumber);for (int j = 0; j < matrix[i].size(); j++) {matrix[i][j].first = INF;matrix[i][j].second = INF;}}for (int i = 0; i < M; i++) {int city1, city2, distance, cost;scanf("%d%d%d%d", &city1, &city2, &distance, &cost);matrix[city1][city2].first = distance;matrix[city1][city2].second = cost;matrix[city2][city1].first = distance;matrix[city2][city1].second = cost;}dijkstra(S);print(S, D);return 0;
}

样例输入

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

样例输出

0 2 3 3 40

鸣谢

PAT

最后

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