Bessie Come Home

Problem Statement

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

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

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

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

Input

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

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

Output

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

Sample Input

1
2
3
4
5
6


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

Sample Output

1

B 11

Solving

基础的单源最短路题目，我们只需要将字符转化为ASCII码来进行建边，并指定字符Z的ASCII码为终点，对所有大写字符作为起点跑最短路，找出所有最短路中的最短路，输出起点字符和路程即可。

注意建边要建双向边，所以链式前向星的edge边数应为MAXM*2!

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101


#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 0;
const int M = 20001;//双向建边注意要乘二 
int t;    
int cnt = 0;
int head[257];
bool vis[257];
ll dis[257];
struct Edge
{
    int next,to,w;
}edge[M];
void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
void init()
{
    for(int i=1;i<=256;i++)
    {
        dis[i] = INF;
    }
    memset(vis,false,sizeof(vis));
}
priority_queue<pii,vector<pii>,greater<pii>> q;
void dijkstra(int start)
{
    dis[start] = 0;
    q.push({0,start});
    while(!q.empty())
    {
        int minnum = q.top().second;
        q.pop();
        if(vis[minnum]) continue;
        vis[minnum] = true;
        for(int i=head[minnum];i;i=edge[i].next)
        {
            int v = edge[i].to;
            int w = edge[i].w;
            if(dis[v]>dis[minnum]+w)
            {
                dis[v] = dis[minnum] + w;
                q.push({dis[v],v});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int m;
    cin >> m;
    vector<pair<char,int>> cattle;
    int end = 'Z';
    for(int i=1;i<=m;i++)
    {
        char a,b;
        cin >> a >> b;
        int A = a;
        int B = b;
        int w;
        cin >> w;
        add(A,B,w);
        add(B,A,w);
        //如果是大写字符则压入起点数组
        if(isupper(a)&&a!='Z') cattle.push_back({a,A});
        if(isupper(b)&&b!='Z') cattle.push_back({b,B});
    }
    vector<pair<char,int>> ans;
    //遍历起点数组，将所有起点跑一遍最短路
    for(pair<char,int> x : cattle)
    {
        int start = x.second;
        char label = x.first;
        init();//注意每跑完一次迪杰斯特拉就要重新初始化Vis和Dis数组
        dijkstra(start);
        ans.push_back({label,dis[end]});
    }
    pair<char,int> answer = {'0',10000000};
    for(pair<char,int> x : ans)//在所有最短路中找出最短的路并记录
    {
        if(x.second < answer.second)
        {
            answer.second = x.second;
            answer.first = x.first;
        }
    }
    cout << answer.first << ' ' << answer.second;
    return 0;
}