<mark>Problem Description</mark>
经过锦囊相助,海东集团终于度过了危机,从此,HDU的发展就一直顺风顺水,到了2050年,集团已经相当规模了,据说进入了钱江肉丝经济开发区500强。这时候,XHD夫妇也退居了二线,并在风景秀美的诸暨市浬浦镇陶姚村买了个房子,开始安度晚年了。
这样住了一段时间,徐总对当地的交通还是不太了解。有时很郁闷,想去一个地方又不知道应该乘什么公交车,在什么地方转车,在什么地方下车(其实徐总自己有车,却一定要与民同乐,这就是徐总的性格)。
徐总经常会问蹩脚的英文问路:“Can you help me?”。看着他那迷茫而又无助的眼神,热心的你能帮帮他吗?
请帮助他用最短的时间到达目的地(假设每一路公交车都只在起点站和终点站停,而且随时都会开)。
<mark>Input</mark>
输入数据有多组,每组的第一行是公交车的总数N(0<=N<=10000);
第二行有徐总的所在地start,他的目的地end;
接着有n行,每行有站名s,站名e,以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note:一组数据中地名数不会超过150个。
如果N==-1,表示输入结束。
<mark>Output</mark>
如果徐总能到达目的地,输出最短的时间;否则,输出“-1”。
<mark>Sample Input</mark>
6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1
<mark>Sample Output</mark>
50
<mark>Hint</mark>
:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake
先说一下解题思路这道题本质上就是一个基础的最短路,Floyd就可以过,但是坑点比较多,所以有人会超时,首先起点和终点是一个字符串,这样我们就用到了map映射,但是接下来注意了,这里面有一个很大的坑,<mark>题目中给出的N并不是节点数,而是边的条数,节点最多有150个,所以初始化图的时候只要初始化150个节点就够了,不然的话只是初始化就炸掉了,再者遍历图中的节点时不要遍历N 切记 切记 切记,,,还有一个坑点就是要注意他是双向图 还有起点和终点相同的处理</mark>
AC 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int maxn = 200;
const int inf = 0x3f3f;
int n, G[maxn][maxn], c, cnt = 1;
string b, e;
map<string, int> m;
void init()
{
for(int i = 1; i <= 155; i++)
{
for(int j = 1; j <= 155; j++)
{
if(i == j)
{
G[i][j] = 0;
}
else
{
G[i][j] = inf;
}
}
}
cnt = 1;
m.clear();
}
void Floyd()
{
for(int k = 1; k <= cnt; k++)
{
for(int i = 1; i <= cnt; i++)
{
for(int j = 1; j<= cnt; j++)
{
if(G[i][j] > G[i][k] + G[k][j])
G[i][j] = G[i][k] + G[k][j];
}
}
}
}
int main()
{
while(scanf("%d", &n) == 1)
{
if(n == -1)
break;
init();
cin >> b >> e;
if(b == e)
{
m[b] = m[e] = cnt++;
}
else
{
m[b] = cnt++;
m[e] = cnt++;
}
int be = m[b], en = m[e];
for(int i = 1; i <= n; i++)
{
cin >> b >> e >> c;
if(!m[b])
m[b] = cnt++;
if(!m[e])
m[e] = cnt++;
if(c < G[m[b]][m[e]])
G[m[b]][m[e]] = G[m[e]][m[b]] = c;
}
Floyd();
if(G[1][2] < inf)
printf("%d\n", G[be][en]);
else
printf("-1\n");
}
}