題目鏈接： http://acm.hdu.edu.cn/showproblem.php?pid=2112
HDU Today
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13396 Accepted Submission(s): 3144
Problem Description
經過錦囊相助，海東集團終於度過了危機，從此，HDU的發展就一直順風順水，到了2050年，集團已經相當規模了，據說進入了錢江肉絲經濟開發區500強。這時候，XHD夫婦也退居了二線，並在風景秀美的諸暨市浬浦鎮陶姚村買了個房子，開始安度晚年了。
這樣住了一段時間，徐總對當地的交通還是不太了解。有時很郁悶，想去一個地方又不知道應該乘什麼公交車，在什麼地方轉車，在什麼地方下車（其實徐總自己有車，卻一定要與民同樂，這就是徐總的性格）。
徐總經常會問蹩腳的英文問路：“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，表示輸入結束。
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 <iostream>
2 #include <cstdio>
3 #include <queue>
4 #include <cstring>
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<node> 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(strcmp(st, ed)==0)
94 {
95 printf("0\n");
96 continue;
97 }
98 Dijkstra(0);
99 if(d[1].key < INF)
100 printf("%d\n", d[1].key);
101 else
102 printf("-1\n");
103 }
104 return 0;
105 }
View Code
