信使 - 题目列表

题目描述

前线有 $n$ 个哨所（ $1 \le n \le 100$ ）和 $m$ 条通信线路，每条线路连接两个哨所，送信需要 $k$ 天。指挥部设在哨所 $1$ ，命令沿线路并行传播。第一行输入 $n,m$ ，随后 $m$ 行每行三个整数 $i,j,k$ 。输出所有哨所都收到命令的最短天数；若有哨所收不到，输出 -1。

样例输入为 4 4 / 1 2 4 / 2 3 7 / 2 4 1 / 3 4 6，输出 11。

思路

每个哨所信使充足，收到信后能同时向所有邻居转发，所以哨所 $v$ 收到命令的时刻就是哨所 $1$ 到 $v$ 的最短路长度，答案取所有最短路的最大值。边权为正，用 Dijkstra 求单源最短路，若某个哨所仍不可达则输出 -1。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#!/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-09-30 07:45
# update_at: 2026-09-30 07:45

import sys
from collections import defaultdict
from heapq import heappop, heappush


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)  # n 个哨所，m 条通信线路（无向边）

    adj: dict[int, list[tuple[int, int]]] = defaultdict(list)
    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        adj[u].append((v, w))  # 无向边两个方向都要登记
        adj[v].append((u, w))

    # Dijkstra：dist[t] = 命令从哨所 1 传到哨所 t 的最短天数
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[1] = 0
    heap = [(0, 1)]
    while heap:
        d, u = heappop(heap)
        if d > dist[u]:
            continue                        # 过期堆项，早已被更短路覆盖
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heappush(heap, (nd, v))

    all_reached = all(d < INF for d in dist[1:])  # 哨所 1 自身必可达
    ans = max(dist[1:]) if all_reached else -1
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * 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:23
 * update_at: 2026-10-05 12:23
 */
// main.cpp：消息从哨所 1 并行扩散，求所有哨所都收到信的最短时间（单源最短路）。
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 105;
const ll INF = (1LL << 60);

int n, m;
ll g[MAXN][MAXN]; // g[u][v] 表示哨所 u 到哨所 v 的通信天数，INF 表示两地无直达线路
ll dist[MAXN];    // dist[v] 表示命令从指挥部（哨所 1）传到哨所 v 的最短天数
int done[MAXN];   // done[v] = 1 表示 v 的最短路已经确定

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            g[i][j] = INF;
        }
        g[i][i] = 0;
    }
    for (int e = 0; e < m; e++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        if (w < g[u][v]) {
            // 线路是双向的，两个方向都要登记；重边取较小的天数
            g[u][v] = w;
            g[v][u] = w;
        }
    }

    // Dijkstra：n 很小，用邻接矩阵每次线性选出未确定点中 dist 最小的即可
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    dist[1] = 0;
    for (int step = 1; step <= n; step++) {
        int u = 0;
        for (int v = 1; v <= n; v++) {
            if (!done[v] && (u == 0 || dist[v] < dist[u])) {
                u = v;
            }
        }
        if (u == 0 || dist[u] == INF) {
            // 剩下的哨所都无法从指挥部到达，提前结束
            break;
        }
        done[u] = 1;
        for (int v = 1; v <= n; v++) {
            if (dist[u] + g[u][v] < dist[v]) {
                dist[v] = dist[u] + g[u][v];
            }
        }
    }

    ll ans = 0; // 全部送达的时刻 = 最晚收到命令的哨所的时刻
    for (int v = 1; v <= n; v++) {
        if (dist[v] == INF) {
            cout << -1 << "\n";
            return 0;
        }
        if (dist[v] > ans) {
            ans = dist[v];
        }
    }
    cout << ans << "\n";
    return 0;
}

信使

目录

题目描述

思路

参考代码