HDU Today
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4841 Accepted Submission(s): 1156
Problem Description
经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。
Input
输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。
Output
如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。
Sample Input
6
xiasha westlake xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1
Sample Output
50
Hint: The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake 虽然偶尔会迷路，但是因为有了你的帮助 **和**从此还是过上了幸福的生活。 ――全剧终――
注意车站数：150
别把M赋值为车的总数了。if (A.[a] == 0) 可以改成if (A.count(a) == 0)后面的也是
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <cstring>
#include <sstream>
#include <fstream>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
//Constant Declaration
/*--------------------------*/
//#define LL long long
#define LL __int64
const int M=160;//最多点数
const int INF=1<<30;
const double EPS = 1e-11;
const double PI = acos(-1.0);
/*--------------------------*/
// some essential funtion
/*----------------------------------*/
void Swap(int &a,int &b){ int t=a;a=b;b=t; }
int Max(int a,int b){ return a>b?a:b; }
int Min(int a,int b){ return a<b?a:b; }
int Gcd(int a,int b){ while(b){b ^= a ^=b ^= a %= b;} return a; }
/*----------------------------------*/
//for (i = 0; i < n; i++)
/*----------------------------------*/
int d[M];//表示i到源点的最短距离
int g[M][M];//邻接矩阵
bool used[M];//标记i是否被用过
void init(int n)
{
int i, j;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
g[i][j] = INF;//初始化图没有边，默认为INF,为了一定更新
}
}
for (i = 1; i <= n; i++)
{
d[i] = INF;
}
memset(used, 0, sizeof(used));
}
int dijkstra(int star, int end, int n)//起点，终点，总点数(编号为1,2...n)
{
int min_num;//最小值的位置
int i;
d[star] = 0;//起点到起点的最短距离为0，很重要的一步
for (int cnt = 0; cnt < n; cnt++)//注意别用while(n--),这样会改变n的值。n次贪心
{
int min = INF;
for (i = 1; i <= n; i++)
{
if (!used[i] && d[i] < min)
{
min = d[i];
min_num = i;
}
}
used[min_num] = 1;
//把d[min_num]作为中间点，对相邻的点做松弛
for (i = 1; i <= n; i++)
{
if (!used[i] && d[i] > d[min_num] + g[min_num][i])
{
d[i] = d[min_num] + g[min_num][i];
}
}
}
return d[end];
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//int t, case1 = 0;
//scanf("%d", &t);
int n, m;
int i, j;
while (~scanf("%d", &n), n != -1)
{
init(150);
map <string, int> A;
string star, end;
int k = 1;
cin >> star >> end;
if (A[star] == 0)//别漏，不然star == end被覆盖
{
A[star] = k++;
}
if (A[end] == 0)
{
A[end] = k++;
}
for (i = 1; i <= n; i++)
{
string a, b;
int c;
cin >> a >> b >> c;
if (A[a] == 0)
{
A[a] = k++;
}
if (A[b] == 0)
{
A[b] = k++;
}
if (g[A[a]][A[b]] > c)
{
g[A[b]][A[a]] = g[A[a]][A[b]] = c;//此题为无向图
}
}
int ans = dijkstra(A[star], A[end], 150);//别写1,2 因为起点和终点可能是同一个位置
if (ans != INF)
{
printf("%d\n", ans);
}
else
{
puts("-1");
}
}
return 0;
}