侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-12-20 / 0 评论 / 0 点赞 / 451 阅读 / 682 字
温馨提示:
本文最后更新于 2022-12-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1507. 旅行计划


给定一张地图,包含 NN 个城市, MM 条高速公路。

城市之间都能相互连通。

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

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

请你确定最短路径,当最短路径不唯一时,请你选取花费最小的路径(保证唯一)。

输入格式

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

城市编号从 00N1N-1

接下来 MM 行,每行包含四个整数 a,b,c,da,b,c,d ,表示城市 aa 和城市 bb 之间存在一条公路,长度为 cc ,花费为 dd

输出格式

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

数据范围

1N5001 \le N \le 500 ,
1M6001 \le M \le 600 ,
1c,d5001 \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;
}
0

评论区