CodeVS 2602 最短路径问题——良心题解

题目描述

给定一个有向无环图，图的每个边都有一个代价，现在要求从起点 $S$ 出发，到达终点 $T$ 的最短路径和。请你求出最短路径和。

题解思路

首先需要明确的是，是有向无环图，因此可以使用拓扑排序来处理每个点的最短路径。同时题目要求求出最短路径和，因此可以使用 Djikstra 算法，使用小根堆来维护节点的优先级，即到起点的距离。

Djikstra 算法的基本思路是从起点出发，每次找到当前未访问节点中到起点距离最短的节点，然后遍历该节点的邻接节点，更新这些邻接节点到起点的距离。这个过程可以使用优先队列（小根堆）来实现，每次从优先队列中取出到起点距离最近的节点，然后更新其邻接节点的距离，再将这些邻接节点加入到优先队列中。

而本题中需要求出最短路径和，因此可以使用数组来记录起点到每个节点的最短路，然后在遍历过程中更新每个节点的最短路径和。

最后，需要注意的是当图中存在多个起点时，需要将所有起点入队，同时起点到起点的最短路初始化为0。

代码实现参见下方。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra() {

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    q.push({0, 1}); //起点为1，距离为0

    memset(dist, 0x3f, sizeof dist); //初始距离为无穷大
    dist[1] = 0;

    while (q.size()) {

        auto t = q.top();
        q.pop();

        int ver = t.second, distance = t.first;
        if (st[ver]) continue; //已确定最短距离，不需要再更新

        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                q.push({dist[j], j});
            }
        }
    }

    cout << dist[n] << endl;
}

int main() {

    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    dijkstra();

    return 0;
}

总结

本题是一道典型的最短路径问题，需要结合 Djikstra 算法和拓扑排序进行解决。同时需要注意当图中存在多个起点时，需要将所有起点入队，同时起点到起点的最短路初始化为0。