这是一道最短路径的变形问题,其中不仅要计算最短的路径,还要在最短路径的基础上计算最小花费,而且要记录所经过的“城市”。总体上来说这是一道“简单”的30分题目。
一些关键代码我给出了注释。注意输出路径的时候,要逆序输出(我用了stack,也可以不用)。
// runtime: 4ms // space: 384K // link: https://pintia.cn/problem-sets/994805342720868352/problems/994805464397627392 // 最短路径的变形题目。 #include <cstring> #include <algorithm> #include <cstdio> #include <vector> #include <climits> #include <queue> #include <stack> using namespace std; const int MAX = 500; const int INF = INT_MAX; struct Edge { int to; int distance; int cost; Edge(int t, int d, int c): to(t), distance(d), cost(c) {} }; struct Point { int number; int distance; Point(int n, int d): number(n), distance(d) {} bool operator< (const Point& p) const { return distance > p.distance; } }; int path[MAX]; // 路径 int dis[MAX]; // 原点到各点的最小距离 int cost[MAX]; // 原点到各点的最小开销 vector<Edge> graph[MAX]; void Dijkstra(int s) { priority_queue<Point> q; dis[s] = 0; cost[s] = 0; q.push(Point(s, dis[s])); while (!q.empty()) { int u = q.top().number; q.pop(); for (int i = 0; i < graph[u].size(); ++i) { int to = graph[u][i].to; int len = graph[u][i].distance; int c = graph[u][i].cost; if (dis[to] > dis[u] + len) { dis[to] = dis[u] + len; cost[to] = cost[u] + c; // 和常规最短路径相比,多记录一下cost q.push(Point(to, dis[to])); path[to] = u; } else if (dis[to] == dis[u] + len && cost[to] > cost[u] + c) { // 和常规最短路径相比,多记录一下cost cost[to] = cost[u] + c; path[to] = u; } } } return ; } int main() { int N, M, S, D; scanf("%d %d %d %d", &N, &M, &S, &D); memset(graph, 0, sizeof(graph)); fill(dis, dis + N, INF); fill(cost, cost + N, INF); for (int i = 0; i < M; ++i) { int from, to, dis, cost; scanf("%d %d %d %d", &from, &to, &dis, &cost); graph[from].push_back(Edge(to, dis, cost)); graph[to].push_back(Edge(from, dis, cost)); } Dijkstra(S); stack<int> s; int d = D; while (d != S) { s.push(path[d]); d = path[d]; } while (!s.empty()) { printf("%d ", s.top()); s.pop(); } printf("%d %d %d", D, dis[D], cost[D]); return 0; }