P1529 [USACO2.4] 回家 Bessie Come Home

题目描述

现在是晚餐时间，而母牛们在外面分散的牧场中。

Farmer John 按响了电铃，所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓（在给出的测试数据中，总会有且只有一只最快的母牛）。在挤奶的时候（晚餐前），每只母牛都在她自己的牧场上，一些牧场上可能没有母牛。

每个牧场由一条条道路和一个或多个牧场连接（可能包括自己）。有时，两个牧场（可能是字母相同的）之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此，所有的母牛最后都能到达谷仓，并且母牛总是走最短的路径。当然，母牛能向着任意一方向前进，并且她们以相同的速度前进。牧场被标记为 $\text{a}\dots \text{z}$ 和 $\text{A}\dots \text{Y}$，在用大写字母表示的牧场中有一只母牛，小写字母中则没有。 谷仓的标记是 $\text{Z}$，注意没有母牛在谷仓中。

注意 $\text{m}$ 和 $\text{M}$ 不是同一个牧场。

输入格式

第一行一个整数 $P$（$1\le P\le 10^4$），表示连接牧场（谷仓）的道路的数目。

接下来 $P$ 行，每行用空格分开的两个字母和一个正整数：被道路连接牧场的标号和道路的长度（道路长度均不超过 $10^3$）。

输出格式

单独的一行包含二个项目：最先到达谷仓的母牛所在的牧场的标号，和这只母牛走过的路径的长度。

输入输出样例 #1

输入 #1

5
A d 6
B d 3
C e 9
d Z 8
e Z 3

输出 #1

B 11

说明/提示

翻译来自 NOCOW

USACO 2.4

C++实现

#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
int dist[60][60];
int getnum(char c){
if(c>=‘a’&&c<=‘z’)return c-‘a’+26;
else return c-‘A’;
}
int main(){
for(int i=0;i<60;i++)for(int j=0;j<60;j++)dist[i][j]=inf-1;
int m;
cin>>m;
while(m–){
string s1,s2;int d;
cin>>s1>>s2>>d;
dist[getnum(s1[0])][getnum(s2[0])]=min(dist[getnum(s1[0])][getnum(s2[0])],d);
dist[getnum(s2[0])][getnum(s1[0])]=min(dist[getnum(s2[0])][getnum(s1[0])],d);
}
for(int k=0;k<60;k++)for(int i=0;i<60;i++)
for(int j=0;j<60;j++)
if(dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];
char ansc;int ans=inf;
for(int i=0;i<25;i++)if(dist[i][25]<=ans){
ans=dist[i][25];ansc=i+‘A’;
}
cout<<ansc<<" "<<ans<<endl;
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容