usaco-2.4.3 回家

题目描述

52 个牧场标记为 a…z、A…Z，其中 A…Y 各有一只母牛，Z 是谷仓。给定 P 条无向正权边（允许重边、自环），所有母牛沿最短路走向谷仓，求最先到达的母牛标记及路径长度。保证最优解唯一。

思路

无向图满足 $\operatorname{dist}(v,Z)=\operatorname{dist}(Z,v)$ ，因此只需从谷仓 Z 跑一次 Dijkstra，再在 A…Y 中取距离最小者即可。重边保留最短一条，正权自环不影响最短路。

参考代码

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
45
46
47
48
49
50
51
52
53
54#!/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-10-01 04:30
# update_at: 2026-10-01 04:30

import sys
from heapq import heappop, heappush

NODE_COUNT = 52              # 牧场标记 a..z 与 A..Z 共 52 个，顶点编号取 0..51
COW_FIRST, BARN = 26, 51     # 有母牛的牧场 A..Y 编号 26..50；编号 51 的 'Z' 是谷仓
INF = 10**18


def node(name: bytes) -> int:
    """把牧场的单字母标记映射成顶点编号：a..z → 0..25，A..Z → 26..51。"""
    return name[0] - 97 if name[0] >= 97 else name[0] - 39  # 'a'=97→0，'A'=65→26


def dijkstra(adj: list[dict[int, int]], src: int) -> list[int]:
    """从 src 出发的单源最短路，返回 52 个牧场的距离（到不了为 INF）。"""
    dist = [INF] * NODE_COUNT
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heappop(heap)
        if d > dist[u]:  # 堆里的过期条目：此后又被更短的路取代过
            continue
        for v, w in adj[u].items():
            if d + w < dist[v]:
                dist[v] = d + w
                heappush(heap, (d + w, v))
    return dist


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    p = int(next(data))  # 题面的道路条数 P
    adj: list[dict[int, int]] = [dict() for _ in range(NODE_COUNT)]
    for _ in range(p):
        u, v = node(next(data)), node(next(data))  # 道路两端的牧场
        w = int(next(data))                        # 道路长度
        # 两个牧场间可能有多条路：只留最短的一条；正权自环不会改进 dist[u]
        adj[u][v] = min(adj[u].get(v, INF), w)
        adj[v][u] = min(adj[v].get(u, INF), w)

    dist = dijkstra(adj, BARN)  # 所有牛都走向谷仓，等价于从谷仓出发算单源最短路
    best = min(range(COW_FIRST, BARN), key=dist.__getitem__)  # 只在 A..Y 里挑最快的
    print(chr(best + 39), dist[best])  # 编号 26..50 还原成 'A'..'Y'


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
81
82
83
84
85
86
87
88
89
90
91
92
93/**
 * 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-06 09:59
 * update_at: 2026-10-06 09:59
 */
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;

const int NODE_COUNT = 52;   // a..z 与 A..Z 共 52 个顶点
const int COW_FIRST = 26;    // 'A' 的编号
const int BARN = 51;         // 'Z' 的编号
const ll INF = (1LL << 60);

// 邻接表：每个顶点保存 (邻居, 权重的最小值)
vector< pair<int, int> > adj[NODE_COUNT];
ll dist[NODE_COUNT];

// 把单字母标记映射成编号：a..z -> 0..25，A..Z -> 26..51
int node_id(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    return c - 'A' + 26;
}

// 从 src 出发的 Dijkstra
void dijkstra(int src) {
    for (int i = 0; i < NODE_COUNT; i++) dist[i] = INF;
    dist[src] = 0;
    priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > q;
    q.push(make_pair(0, src));
    while (!q.empty()) {
        pair<ll, int> cur = q.top(); q.pop();
        ll d = cur.first;
        int u = cur.second;
        if (d > dist[u]) continue; // 过期条目
        for (int i = 0; i < (int)adj[u].size(); i++) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                q.push(make_pair(dist[v], v));
            }
        }
    }
}

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

    int p;
    if (!(cin >> p)) return 0;
    // 先用临时数组去重边（保留最小权重）
    int tmp[NODE_COUNT][NODE_COUNT];
    for (int i = 0; i < NODE_COUNT; i++)
        for (int j = 0; j < NODE_COUNT; j++)
            tmp[i][j] = -1;

    for (int i = 0; i < p; i++) {
        char cu, cv;
        int w;
        cin >> cu >> cv >> w;
        int u = node_id(cu);
        int v = node_id(cv);
        if (tmp[u][v] == -1 || w < tmp[u][v]) {
            tmp[u][v] = w;
            tmp[v][u] = w;
        }
    }

    for (int u = 0; u < NODE_COUNT; u++) {
        for (int v = 0; v < NODE_COUNT; v++) {
            if (tmp[u][v] != -1) {
                adj[u].push_back(make_pair(v, tmp[u][v]));
            }
        }
    }

    dijkstra(BARN); // 无向图，从谷仓出发一次即可

    int best = COW_FIRST;
    for (int v = COW_FIRST + 1; v < BARN; v++) { // 只在 A..Y 里找
        if (dist[v] < dist[best]) best = v;
    }

    cout << (char)(best + 'A' - 26) << ' ' << dist[best] << '\n';
    return 0;
}

目录

题目描述

思路

参考代码