题目链接

题目描述

给定由 个顶点、 条边构成的有向赋权图（不一定连通），边权为非负整数。给定起点 ，依次输出从 到每个顶点的最短路径长度；若不可达输出 ，到自身输出 。允许重边，无自环。

解题思路

  • 非负权最短路 = 堆优化 Dijkstra：对于非负边权，采用 Dijkstra 算法配合优先队列（小根堆）可在 时间内求出单源最短路。
  • 做法：
    • 建邻接表。距离数组 初始为 ，。
    • 用小根堆按当前最短距离取出顶点 ，若弹出的距离大于已知 则跳过；否则对每条出边 进行松弛：若 ，则更新并入堆。
    • 结束后， 的顶点输出 。
  • 细节：
    • 边权可能为 ，Dijkstra 依然适用。
    • 建议使用 64 位整型存储距离，避免累加溢出。

代码

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<pair<int,int>>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    const long long INF = (1LL << 62);
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue; // 过期状态
        for (auto [v, w] : g[u]) {
            long long nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (i > 1) cout << ' ';
        cout << (dist[i] == INF ? -1 : (long long)dist[i]);
    }
    cout << '\n';
    return 0;
}

import java.util.*;

public class Main {
    static class Edge { int v, w; Edge(int v, int w){ this.v=v; this.w=w; } }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int s = sc.nextInt();
        List<Edge>[] g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
            g[u].add(new Edge(v, w));
        }
        final long INF = 1L << 62;
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        dist[s] = 0;
        pq.add(new long[]{0L, s});
        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0];
            int u = (int)cur[1];
            if (d != dist[u]) continue;
            for (Edge e : g[u]) {
                long nd = d + e.w;
                if (nd < dist[e.v]) {
                    dist[e.v] = nd;
                    pq.add(new long[]{nd, e.v});
                }
            }
        }
        StringBuilder out = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) out.append(' ');
            out.append(dist[i] == INF ? -1 : dist[i]);
        }
        System.out.println(out);
    }
}

import sys
import heapq

data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it)); m = int(next(it)); s = int(next(it))
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u = int(next(it)); v = int(next(it)); w = int(next(it))
    g[u].append((v, w))

INF = 1 << 62
dist = [INF] * (n + 1)
dist[s] = 0
pq = [(0, s)]
while pq:
    d, u = heapq.heappop(pq)
    if d != dist[u]:
        continue
    for v, w in g[u]:
        nd = d + w
        if nd < dist[v]:
            dist[v] = nd
            heapq.heappush(pq, (nd, v))

print(' '.join(str(-1 if dist[i] == INF else dist[i]) for i in range(1, n + 1)))

算法及复杂度

  • 算法：堆优化 Dijkstra，使用小根堆维护当前最短的候选顶点，进行松弛更新。
  • 时间复杂度：。
  • 空间复杂度：。