一眼dijkstars,把Z当作起点,再分别比较Z到其他大写字母的距离取最小,
主要注意图的建立和存储
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
int n;
int g[N][N], dist[N];
bool st[N];
int get(char c)
{
if (c <= 'Z') return c - 'A' + 1;
return c - 'a' + 27;
}
void dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[26]=0;//Z为起点
for(int i=0;i<51;i++){
int t=-1;
for(int j=1;j<=52;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
st[t]=true;
for(int j=1;j<=52;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
}
int main()
{
cin>>n;
memset(g, 0x3f, sizeof g);
while (n -- )
{
char a, b;
int c;
cin >> a >> b >> c;
int x = get(a), y = get(b);
g[x][y] = g[y][x] = min(c, g[x][y]);
}
dijkstra();
int res=dist[1];
char ans = (char)(1+'A'-1);
for(int i=1;i<=25;i++){
if(dist[i]<res){
res=dist[i];
ans=i+'A'-1;
}
}
cout << ans<<" "<<res<<endl;
}