晚餐时间即将到来,奶牛们正在各自的牧场漫步。当农夫约翰摇动铃铛时,这些奶牛必须返回牛棚进餐。

在晚餐前,所有奶牛都分布在不同的牧场,有些牧场可能没有奶牛。这些牧场之间通过道路相互连接,有时两个牧场之间有多条道路。

至少有一个牧场直接与牛棚相连,确保所有奶牛能够成功返回牛棚。

奶牛们总是会选择最短路径回到牛棚,所有道路都是双向通行,奶牛的速度相同。

我们用大写字母 A 到 Y 标记有奶牛的牧场,用小写字母 a 到 z 标记没有奶牛的牧场,牛棚标记为 Z,最初没有奶牛在牛棚。

现在你需要找出哪头奶牛能够最快回到牛棚,输出它最初所在的牧场标记以及它走过的路径长度。

注意,大小写字母标记的两个不同牧场(如 A 和 a)是完全不同的牧场。

输入格式:

  • 第一行包含整数 P,表示连接牧场与牛棚的道路数量。
  • 接下来 P 行,每行包含两个字母标记的牧场以及一个整数,表示连接两个牧场的道路标记和道路长度。

输出格式:

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

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

数据范围:

  • 1 ≤ P ≤ 10,000
  • 所有道路长度不超过 1,000

示例输入:

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

示例输出:

B 11

题目分析

Dijikstra

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 200;

int a, b, c, p, dist[N], st[N], g[N][N];
void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist['Z'] = 0;
    for (int i = 'A'; i < 'z'; ++i) {
        int t = -1;
        for (int j = 'A'; j <= 'z'; ++j) {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        for (int j = 'A'; j < 'Z'; ++j) {
            if (!st[j] && (dist[j] == dist[t])) {
                cout << (char)t << ' ' << dist[t];
                return ;
            }   
        }
        st[t] = 1;
        for (int j = 'A'; j <= 'z'; ++j) {
            if (!st[j]) dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(g, 0x3f, sizeof g);
    for (int i = 'A'; i <= 'z'; ++i) g[i][i] = 0;
    cin >> p;
    while(p--) {
        char a, b;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(min(g[a][b],g[b][a]),c);
    }
    dijkstra();
    return 0;
}
分类: Dijkstra

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status