题目描述
晚餐时间马上就到了,奶牛们还在各自的牧场中悠闲的散着步。
当农夫约翰摇动铃铛,这些牛就要赶回牛棚去吃晚餐。
在吃晚餐之前,所有奶牛都在自己的牧场之中,有些牧场中可能没有奶牛。
每个牧场都通过一条条道路连接到一个或多个其他牧场(可能包括其自身)。
有时,两个(可能是相同的)牧场通过一条以上的道路相连。
至少存在一个牧场与牛棚通过一条道路直接相连。
所以说,所有奶牛都能够成功的从自己的牧场沿道路返回牛棚。
聪明的奶牛们总会选择最短的路径回到牛棚之中。
每条道路都是可以双向行走的,奶牛的行走速度也都一样。
我们用 a∼z 和 A∼Y 来标记所有的牧场。
所有用大写字母标记的牧场中都存在一头奶牛,所有用小写字母标记的牧场中都不存在奶牛。
牛棚的标记为 Z,这里最初是没有奶牛的。
现在你需要确定,哪一头奶牛能够最快到达牛棚,输出它最初所在的牧场的标记,并输出它走过的路径的长度。
注意,同一字母大小写标记的两个牧场(例如,牧场A和牧场a是两个完全不同的牧场)
样例
5
A d 6
B d 3
C e 9
d Z 8
e Z 3
朴素dijkstra(邻接矩阵)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
/*
最终都要回到牛棚,那就可以将牛棚Z看作源点
不知道有多少个节点,他不是给你固定了是a~z, A~Z嘛,总共就52个
就把这些字母规定在一个区间范围内呗
满打满算52 * 52 , 10000条边,老稠密了
*/
const int N = 60;
int g[N][N];
int dist[N];
bool st[N];
int n;
int get(char a){
if(a > 'Z') return a - 'a' + 1 + 26;
else return a - 'A' + 1;
/*
1~26: A ~ Z ; 27 ~ 52: a ~ z
*/
}
void dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[26] = 0; // Z作为源点
for(int i = 0; i < 52; ++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(){
scanf("%d", &n);
memset(g, 0x3f, sizeof g);
while(n --){
char a, b;
int c;
cin >> a >> b >> c;
int x = get(a);
int y = get(b);
g[x][y] = g[y][x] = min(g[x][y], c);
}
dijkstra();
int k = 1;
//只有大写字母的才有牛
for(int i = 1; i <= 25; ++i){ //Z(26)作为源点,我不打扰
if(dist[i] < 0x3f3f3f3f / 2 && dist[k] > dist[i]) k = i;
}
cout << char(k + 'A' - 1) << ' ' << dist[k]; //因为规定为1~26,所以作为结果就减去1
return 0;
}
邻接表 + 堆
超时,悲
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
/*
8/9 超时 不管是cin 还是 scanf
*/
typedef pair<int, int> PII;
const int N = 1e4 + 5;
int h[N], e[N], ne[N], w[N], idx;
int dist[60];
bool st[60];
int n;
int get(char a){
/*
1~26 A ~ Z
27 ~ 52 a ~ z
*/
if(a > 'Z') return a - 'a' + 1 + 26;
else return a - 'A' + 1;
}
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[26] = 0; //Z是源点
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 26});
while(heap.size()){
auto t = heap.top();
heap.pop();
int ver = t.second, dis = t.first;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > dis + w[i]){
dist[j] = dis + w[i];
heap.push({dist[j], j});
}
}
}
}
int main(){
int n; scanf("%d", &n);
memset(h, -1, sizeof h);
while(n --){
char a, b;
int c;
scanf("\n%c %c %d", &a, &b, &c);
//cin >> a >> b >> c;
int x = get(a);
int y = get(b);
add(x, y, c);
add(y, x, c);
}
dijkstra();
int k = 1;
for(int i = 1; i <= 25; ++i){ //题目中说只有大写字母的才有牛
if(dist[i] < 0x3f3f3f3f / 2 && dist[k] > dist[i]){
k = i;
}
}
cout << char(k + 'A' - 1) <<' '<< dist[k] << '\n';
return 0;
}