城市路（Dijkstra）

GitHub跳转原题关系图返回列表

无向带重边图上跑堆优化 Dijkstra，边权非负时第一次弹出 n 即最短路，不可达输出 -1。

OJ: roj

题目 ID: 1381

难度:普及-

标签:最短路Dijkstra堆图论python

创建: 2026-07-05 21:47

更新: 2026-10-05 12:30

后置题目
roj 2051香甜的黄油B 每枚举一个候选放糖点就跑一次与 A 完全同款的堆优化 Dijkstra（含 `if d > dist[u]: continue` 跳过过期堆记录这一步），A 只求 1 到 n 单条最短路，B 在此之上叠加无向图对称换向、按牛数加权求和与枚举全部牧场取 min。luogu P3003[USACO10DEC] Apple Delivery SB 的直接复用 A 教的堆优化 Dijkstra——main.cpp 的 dijkstra() 就是 A 的小根堆按 dist 出队模板，B 只是把它调用两次求出 PB、PA1 到两送货点的距离，再叠加「只有两种送货顺序取较小值」这一步额外流程。

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

给定 nn 个城市、mm 条双向道路，求从城市 11 到城市 nn 的最短距离；若不可达输出 -1。

输入：n mn\ m，随后 mm 行每行 a b c 表示城市 aa、bb 间有一条长度为 cc 的路。

数据范围：1≤n≤20001 \le n \le 2000，1≤m≤100001 \le m \le 10000，0≤c≤100000 \le c \le 10000。

样例输入：

text
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

样例输出：

text
90

思路

边权非负，用堆优化 Dijkstra：用邻接表存无向图，小根堆按当前距离取点，第一次弹出城市 nn 时即为最短路；不可达输出 -1。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import heapq
import sys


def solve() -> None:
    """堆优化 Dijkstra：求 1 到 n 的最短路，不可达输出 -1。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 邻接表：每条无向边存两次
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b, c = next(data), next(data), next(data)
        adj[a].append((b, c))  # a -> b
        adj[b].append((a, c))  # b -> a

    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[1] = 0
    heap = [(0, 1)]  # (距离, 点)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:  # 过期堆元素，跳过
            continue
        if u == n:
            break  # 第一次弹出即最短，提前结束
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))

    print(dist[n] if dist[n] < INF else -1)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:30
 * update_at: 2026-10-05 12:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;           // 数据默认 long long
const ll INF = 1e18;            // 不可达标记
const int MAXN = 2005;          // 最多 n 个点

int n, m;
ll dist_arr[MAXN];              // dist_arr[i] 表示 1 到 i 的当前最短距离

// 邻接表：g[i] 存 (邻居, 边权)
vector<pair<int, int> > g[MAXN];

// 堆优化 Dijkstra：第一次弹出 n 即可返回最短距离，不可达返回 INF
ll dijkstra() {
    for (int i = 1; i <= n; i++) dist_arr[i] = INF;
    dist_arr[1] = 0;

    // 小根堆：按当前距离排序
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;
    q.push(make_pair(0, 1));

    while (!q.empty()) {
        pair<ll, int> cur = q.top();
        q.pop();
        ll d = cur.first;
        int u = cur.second;

        if (d > dist_arr[u]) continue;          // 过期记录，跳过
        if (u == n) return d;                   // 第一次弹出 n，已确定最短

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i].first;
            int w = g[u][i].second;
            if (dist_arr[u] + w < dist_arr[v]) {
                dist_arr[v] = dist_arr[u] + w;
                q.push(make_pair(dist_arr[v], v));
            }
        }
    }
    return INF;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        g[a].push_back(make_pair(b, c));
        g[b].push_back(make_pair(a, c));        // 无向图存反向边
    }

    ll ans = dijkstra();
    if (ans == INF) printf("-1\n");
    else printf("%lld\n", ans);
    return 0;
}