模板题。。
传送门：codevs 1079
思路 ：以 Z 为起点 直接跑一边SPFA , 看哪一头母牛距离Z点最近 ， 最后找出Z 到 A~Y 的最短路 （因为仅有A~Z有奶牛）
#include <iostream>
#include <cstdio>
#include <cstring>
#define Max 300000
#define INF 100000000
using namespace std;
int N, Count;
int head [Max], dis [Max], queue [Max];
bool visit [Max];
struct node
{
int to;
int dis;
int next;
}Edge [Max];
void AddEdge (int x, int y, int w)
{
Count++;
Edge [Count].to = y;
Edge [Count].dis = w;
Edge [Count].next = head [x];
head [x] = Count;
}
void SPFA (int start)
{
int head_cur = , tail_cur = ;
for (int i = ; i <= ; i++)
{
dis [i] = INF;
visit [i] = false;
}
dis [start] = ;
queue [] = start;
while (head_cur <= tail_cur)
{
head_cur++;
int now = queue [head_cur];
for (int i = head [now]; i; i = Edge [i].next)
if (dis [now] + Edge[i].dis < dis [Edge [i].to])
{
dis [Edge [i].to] = dis [now] + Edge[i].dis ;
if (visit [Edge[i].to ] == false)
{
queue [++tail_cur] = Edge [i].to;
visit [Edge[i].to ] = true;
}
}
visit [now] = false;
}
}
int main()
{
ios :: sync_with_stdio (false);
cin >> N;
char x, y;
int w;
for (int i = ; i <= N; i++)
{
cin >> x >> y >> w;
AddEdge ((int) (x), (int) (y), w); //直接用 字母 的Ascll 码 作为节点即可
AddEdge ((int) (y), (int) (x), w);
}
SPFA ((int)'Z');
int flag, Maxn = INF;
for (int i = 'A'; i <= 'Y'; i++) //因为只有A ~ Y 有母牛，所以只需查找这些点即可
{
if (dis [i] < Maxn)
{
Maxn = dis [i];
flag = i; //找出距离最短的点
}
}
cout << (char)flag << " " << dis [flag];
return ;
}