牧场总数只有 52 个，把大小写字母映射成编号后直接 Floyd 求全源最短路，再在 A..Y 中找离 Z 最近的那头牛。
OJ: luogu
题目 ID: P1529
难度:普及-
标签:最短路图论Floyd
日期: 2026-06-20 03:29
题意
牧场用字母表示：
a..zA..YZ
其中：
- 大写
A..Y上各有一头牛 Z是谷仓- 小写字母上没有牛
给若干条无向边和边权。
所有牛都要走最短路回到 Z。
要求输出：
- 最先回到谷仓的那头牛所在的大写牧场字母
- 它到
Z的最短路长度
思路
先看一个最直接的小数据暴力：
cpp
// brute.cpp：对每头有牛的大写牧场各跑一次 Dijkstra，直接比较谁到 Z 最近。
// 小数据下很好理解，也方便对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 52;
const int MAXM = 4005;
const int INF = 1e9;
struct HeapNode {
int u;
int dist;
bool operator < (const HeapNode &other) const {
return dist > other.dist;
}
};
int p;
int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM], edge_cnt;
int dist_arr[MAXN];
bool vis[MAXN];
int char_to_id(char ch) {
if ('a' <= ch && ch <= 'z') {
return ch - 'a';
}
return ch - 'A' + 26;
}
char id_to_char(int id) {
if (id < 26) {
return char('a' + id);
}
return char('A' + (id - 26));
}
void add_edge(int u, int v, int len) {
edge_cnt++;
to[edge_cnt] = v;
w[edge_cnt] = len;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void dijkstra(int start) {
for (int i = 0; i < MAXN; i++) {
dist_arr[i] = INF;
vis[i] = false;
}
priority_queue<HeapNode> pq;
dist_arr[start] = 0;
pq.push({start, 0});
while (!pq.empty()) {
HeapNode cur = pq.top();
pq.pop();
int u = cur.u;
if (vis[u]) {
continue;
}
vis[u] = true;
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
int nd = dist_arr[u] + w[i];
if (nd < dist_arr[v]) {
dist_arr[v] = nd;
pq.push({v, nd});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> p;
for (int i = 0; i < MAXN; i++) {
head[i] = 0;
}
edge_cnt = 0;
for (int i = 1; i <= p; i++) {
char a, b;
int len;
cin >> a >> b >> len;
int u = char_to_id(a);
int v = char_to_id(b);
add_edge(u, v, len);
add_edge(v, u, len);
}
int z_id = char_to_id('Z');
int answer_id = -1;
int answer_dist = INF;
for (int i = char_to_id('A'); i < z_id; i++) {
dijkstra(i);
if (dist_arr[z_id] < answer_dist) {
answer_dist = dist_arr[z_id];
answer_id = i;
}
}
cout << id_to_char(answer_id) << ' ' << answer_dist << '\n';
return 0;
}暴力做法是：
- 对每个大写牧场
A..Y单独跑一次 Dijkstra - 看谁到
Z最近
这个做法已经可以过小数据，也很好理解。
但这题最关键的观察是：
- 整张图的点其实只有
26 + 26 = 52个
也就是说，虽然输入看起来像字符串图，但本质上只是一个很小的图。
这时直接做 Floyd 反而最自然：
- 先把字符映射成
0..51的编号 - 建一个
52 x 52的距离矩阵 - Floyd 求任意两点最短路
- 枚举所有有牛的大写点
A..Y，找dist[i][Z]最小的那个
这里要注意两点：
1. 大小写是不同的点
m 和 M 不是同一个牧场，所以必须分开编号。
2. 只有 A..Y 上有牛
Z 是谷仓，没有牛在 Z 上。
所以最后枚举答案时只看：
A到Y
不看 Z。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 52;
const int INF = 1e9;
int p;
int dist_arr[MAXN][MAXN];
int char_to_id(char ch) {
if ('a' <= ch && ch <= 'z') {
return ch - 'a';
}
return ch - 'A' + 26;
}
char id_to_char(int id) {
if (id < 26) {
return char('a' + id);
}
return char('A' + (id - 26));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> p;
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
if (i == j) {
dist_arr[i][j] = 0;
}
else {
dist_arr[i][j] = INF;
}
}
}
for (int i = 1; i <= p; i++) {
char a, b;
int w;
cin >> a >> b >> w;
int u = char_to_id(a);
int v = char_to_id(b);
if (w < dist_arr[u][v]) {
dist_arr[u][v] = w;
dist_arr[v][u] = w;
}
}
// 点数只有 52，直接 Floyd 求任意两点最短路最省事。
for (int k = 0; k < MAXN; k++) {
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
if (dist_arr[i][k] + dist_arr[k][j] < dist_arr[i][j]) {
dist_arr[i][j] = dist_arr[i][k] + dist_arr[k][j];
}
}
}
}
int z_id = char_to_id('Z');
int answer_id = -1;
int answer_dist = INF;
// 只有 A..Y 上有牛，Z 是谷仓，不参与比较。
for (int i = char_to_id('A'); i < z_id; i++) {
if (dist_arr[i][z_id] < answer_dist) {
answer_dist = dist_arr[i][z_id];
answer_id = i;
}
}
cout << id_to_char(answer_id) << ' ' << answer_dist << '\n';
return 0;
}复杂度
Floyd 的时间复杂度：
这在本题里就是一个很小的常数。
空间复杂度：
总结
这题最重要的不是最短路模板本身，而是先看清楚：
- 点数其实只有 52
一旦意识到图很小，Floyd 就是最顺手的写法。
所以这是一个很典型的“先估点数，再选最短路算法”的题。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
