AcWing 1375. 奶牛回家
原题链接
简单
作者:
Asiryk
,
2024-04-11 17:13:40
,
所有人可见
,
阅读 4
(Floyd) $O(n^3)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 110;
int g[N][N];
int m;
// 'a' - 'z' 26 - 52
// 'A' - 'Z' 0 - 25
int ctoi(char x){
if(x >= 'a' && x <= 'z') x = x - 'a' + 26;
if(x >= 'A' && x <= 'Z') x -= 'A';
return x;
}
char itoc(int x){
if(x >= 0 && x < 26) return x + 'A';
else return x + 'a' - 26;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
memset(g,0x3f,sizeof g);
for(int i = 0;i < N;i++) g[i][i] = 0;
cin >> m;
char x,y;
int w;
for(int i = 1;i<=m;i++){
cin >> x >> y >> w;
g[ctoi(x)][ctoi(y)] = min(g[ctoi(x)][ctoi(y)],w);
g[ctoi(y)][ctoi(x)] = min(g[ctoi(y)][ctoi(x)],w);
}
for(int k = 0;k <= 52;k++){
for(int i = 0;i<=52;i++){
for(int j = 0;j<=52;j++){
g[i][j] = min(g[i][j],g[i][k] + g[k][j]);
}
}
}
int minn = 0x3f3f3f3f;
char p;
for(int i = 0;i < 25;i++){
if(minn > g[i][25]){
minn = g[i][25];
p = itoc(i);
}
}
cout<<p<<" "<<minn<<endl;
return 0;
}