【最短路, Dijkstra算法】奶牛回家

题目

1375. 奶牛回家

---

晚餐时间马上就到了，奶牛们还在各自的牧场中悠闲的散着步。

当农夫约翰摇动铃铛，这些牛就要赶回牛棚去吃晚餐。

在吃晚餐之前，所有奶牛都在自己的牧场之中，有些牧场中可能没有奶牛。

每个牧场都通过一条条道路连接到一个或多个其他牧场（可能包括其自身）。

有时，两个（可能是相同的）牧场通过一条以上的道路相连。

至少存在一个牧场与牛棚通过一条道路直接相连。

所以说，所有奶牛都能够成功的从自己的牧场沿道路返回牛棚。

聪明的奶牛们总会选择最短的路径回到牛棚之中。

每条道路都是可以双向行走的，奶牛的行走速度也都一样。

我们用 $a \sim z$ 和 $A \sim Y$ 来标记所有的牧场。

所有用大写字母标记的牧场中都存在一头奶牛，所有用小写字母标记的牧场中都不存在奶牛。

牛棚的标记为 $Z$ ，这里最初是没有奶牛的。

现在你需要确定，哪一头奶牛能够最快到达牛棚，输出它最初所在的牧场的标记，并输出它走过的路径的长度。

注意，同一字母大小写标记的两个牧场（例如，牧场 $A$ 和牧场 $a$ ）是两个完全不同的牧场。

输入格式

第一行包含整数 $P$ ，表示连接牧场以及牛棚的道路的条数。

接下来 $P$ 行，每行包含两个字母以及一个整数，表示被一条道路连接的两个牧场的标记，以及这条道路的长度。

输出格式

输出一个字母和一个整数，表示最快回到牛棚的牛最初所在的牧场的标记以及它走过的路径的长度。

数据保证最快回到牛棚的牛只有一头。

数据范围

$1 \le P \le 10000$ ,
所有道路长度均不超过 $1000$ 。

输入样例：

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

输出样例：

B 11

解题

方法一：Dijkstra算法

思路

对每一对奶牛和牛棚跑一次最短路，并记录距离最短的。

代码

#include <iostream>
#include <cstring>
#include <limits>
#include <unordered_map>
#include <vector>

using namespace std;

const int N = 60, INF = 0x3f3f3f3f;
unordered_map<char, int> mp;
vector<char> cows;
int p, n, g[N][N], dists[N];
bool vis[N];

int dijkstra(int ori, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    memset(vis, 0, sizeof(vis));
    dists[ori] = 0;
    for (int i = 1; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) {
            dists[j] = min(dists[j], dists[mn] + g[mn][j]);
        }
    }
    return dists[dest];
}

int main() {
    scanf("%d", &p);
    memset(g, 0x3f, sizeof(g));
    mp['Z'] = ++n;
    while (p--) {
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        char u, v;
        int w;
        scanf("%c %c %d", &u, &v, &w);
        if (mp.find(u) == mp.end()) mp[u] = ++n;
        if (mp.find(v) == mp.end()) mp[v] = ++n;
        int a = mp[u], b = mp[v];
        g[a][b] = g[b][a] = min(g[a][b], w);
        if (u >= 'A' && u < 'Z') cows.push_back(u);
        if (v >= 'A' && v < 'Z') cows.push_back(v);
    }
    char mn_cow;
    int mn_dist = INF;
    for (auto& cow : cows) {
        int dist = dijkstra(mp[cow], 1);
        if (dist < mn_dist) {
            mn_cow = cow;
            mn_dist = dist;
        }
    }
    printf("%c %d\n", mn_cow, mn_dist);
    
    return 0;
}