【最短路, Dijkstra算法】旅行计划

题目

1507. 旅行计划

---

给定一张地图，包含 $N$ 个城市， $M$ 条高速公路。

城市之间都能相互连通。

每条高速公路的长度和走该条公路的花费都是已知的，高速公路都是双向的。

现在要从地图中的某个城市前往另一个城市。

请你确定最短路径，当最短路径不唯一时，请你选取花费最小的路径（保证唯一）。

输入格式

第一行包含四个整数 $N,M,S,D$ ，分别表示城市数量，公路数量，起点城市编号，终点城市编号。

城市编号从 $0$ 到 $N-1$ 。

接下来 $M$ 行，每行包含四个整数 $a,b,c,d$ ，表示城市 $a$ 和城市 $b$ 之间存在一条公路，长度为 $c$ ，花费为 $d$ 。

输出格式

共一行，首先输出从起点城市到终点城市的最短路径（花费最少的）经过的所有城市，然后输出最短路径的距离以及最小的花费。

数据范围

$1 \le N \le 500$ ,
$1 \le M \le 600$ ,
$1 \le c,d \le 500$

输入样例：

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

解题

方法一：Dijkstra算法

思路

朴素 Dijkstra 算法。

代码

#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m, s, d, g[N][N], c[N][N];
int dists[N], costs[N], prevs[N];
bool vis[N];

void dijkstra(int ori, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    memset(costs, 0x3f, sizeof(costs));
    memset(prevs, -1, sizeof(prevs));
    dists[ori] = costs[ori] = 0;
    for (int i = 1; i < n; ++i) {
        int mn = -1;
        for (int j = 0; j < n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        vis[mn] = true;
        for (int j = 0; j < n; ++j) {
            int ind_dist = dists[mn] + g[mn][j], ind_cost = costs[mn] + c[mn][j];
            if (ind_dist < dists[j] || (ind_dist == dists[j] && ind_cost < costs[j])) {
                dists[j] = ind_dist;
                costs[j] = ind_cost;
                prevs[j] = mn;
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &d);
    memset(g, 0x3f, sizeof(g));
    memset(c, 0x3f, sizeof(c));
    while (m--) {
        int a, b, dist ,cost;
        scanf("%d%d%d%d", &a, &b, &dist, &cost);
        g[a][b] = g[b][a] = min(g[a][b], dist);
        c[a][b] = c[b][a] = min(c[a][b], cost);
    }
    dijkstra(s, d);
    stack<int> path;
    for (int i = d; ~i; i = prevs[i]) path.push(i);
    while (!path.empty()) {
        printf("%d ", path.top()), path.pop();
    }
    printf("%d %d\n", dists[d], costs[d]);

    return 0;
}