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 虽然偶尔会迷路，但是因为有了你的帮助 **和**从此还是过上了幸福的生活。 ??全剧终??
?
分析：题目意思很简单，求最短路，要注意的是顶点名称都换成了字符串，要重新标记，还有就是起点和终点重合的情况需要考虑。
问题：用string来存储字符串应该是很方便的，但是不知道为什么全部用string来表示，用cin输入无限超时啊。后面改为字符数组了然后用scanf居然就过了，太坑爹。
?
代码如下：
? 1 #include
? 2 #include
? 3 #include
? 4 #include
? 5 using namespace std;
? 6?
? 7 #define maxn 155
? 8 #define INF 10000000
? 9 int w[maxn][maxn];
?10?
?11 struct node
?12 {
?13 ? ? int u, key;
?14 ? ? friend bool operator<(node a, node b)
?15 ? ? {
?16 ? ? ? ? return a.key > b.key;
?17 ? ? }
?18 };
?19?
?20 bool visited[maxn];
?21 node d[maxn];
?22 priority_queue q;
?23 char stn[maxn][35];
?24 int sno;
?25 void Dijkstra(int s)
?26 {
?27 ? ? for(int i = 0; i < sno; i++)
?28 ? ? {
?29 ? ? ? ? d[i].u = i;
?30 ? ? ? ? d[i].key = INF;
?31 ? ? ? ? visited[i] = false;
?32 ? ? }
?33 ? ? d[s].key = 0;
?34 ? ? q.push(d[s]);
?35 ? ? while(!q.empty())
?36 ? ? {
?37 ? ? ? ? node nd = q.top();
?38 ? ? ? ? q.pop();
?39 ? ? ? ? int st = nd.u;
?40 ? ? ? ? if(visited[st] == true)
?41 ? ? ? ? ? ? continue;
?42 ? ? ? ? visited[st] = true;
?43 ? ? ? ? for(int j = 0; j < sno; j++)
?44 ? ? ? ? {
?45 ? ? ? ? ? ? if(j!=st && !visited[j] && w[st][j]+d[st].key < d[j].key)
?46 ? ? ? ? ? ? {
?47 ? ? ? ? ? ? ? ? d[j].key = w[st][j]+d[st].key;
?48 ? ? ? ? ? ? ? ? q.push(d[j]);
?49 ? ? ? ? ? ? }
?50 ? ? ? ? }
?51 ? ? }
?52 }
?53?
?54 int Find(char s[])
?55 {
?56 ? ? for(int i = 0; i < sno; i++)
?57 ? ? ? ? if(strcmp(stn[i], s)==0)
?58 ? ? ? ? ? ? return i;
?59 ? ? return -1;
?60 }
?61 int main()
?62 {
?63 ? ? int n, c, x, y;
?64 ? ? char st[35], ed[35], a[35], b[35];
?65 ? ? while(scanf("%d", &n), n!=-1)
?66 ? ? {
?67 ? ? ? ? for(int i = 0; i <= maxn; i++)
?68 ? ? ? ? ? ? for(int j = i; j <= maxn; j++)
?69 ? ? ? ? ? ? ? ? w[i][j] = w[j][i] = INF;
?70 ? ? ? ? scanf("%s%s", st, ed);
?71 ? ? ? ? strcpy(stn[0], st);
?72 ? ? ? ? strcpy(stn[1], ed);
?73 ? ? ? ? sno = 2;
?74 ? ? ? ? while(n--)
?75 ? ? ? ? {
?76 ? ? ? ? ? ? scanf("%s %s %d", a, b, &c);
?77 ? ? ? ? ? ? x = Find(a);
?78 ? ? ? ? ? ? if(x == -1)
?79 ? ? ? ? ? ? {
?80 ? ? ? ? ? ? ? ? x = sno;
?81 ? ? ? ? ? ? ? ? //stn[sno++] = a;
?82 ? ? ? ? ? ? ? ? strcpy(stn[sno++], a);
?83 ? ? ? ? ? ? }
?84 ? ? ? ? ? ? y = Find(b);
?85 ? ? ? ? ? ? if(y == -1)
?86 ? ? ? ? ? ? {
?87 ? ? ? ? ? ? ? ? y = sno;
?88 ? ? ? ? ? ? ? ? strcpy(stn[sno++], b);
?89 ? ? ? ? ? ? }
?90 ? ? ? ? ? ? if(w[x][y] > c)
?91 ? ? ? ? ? ? ? ? w[x][y] = w[y][x] = c;
?92 ? ? ? ? }
?93 ? ? ? ? if(s