HDU Today

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Time Limit: 15000/5000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)

Problem Description 經(jīng)過錦囊相助，海東集團終于度過了危機，從此，HDU的發(fā)展就一直順風順水，到了2050年，集團已經(jīng)相當規(guī)模了，據(jù)說進入了錢江肉絲經(jīng)濟開發(fā)區(qū)500強。這時候，XHD夫婦也退居了二線，并在風景秀美的諸暨市浬浦鎮(zhèn)陶姚村買了個房子，開始安度晚年了。
這樣住了一段時間，徐總對當?shù)氐慕煌ㄟ€是不太了解。有時很郁悶，想去一個地方又不知道應該乘什么公交車，在什么地方轉(zhuǎn)車，在什么地方下車（其實徐總自己有車，卻一定要與民同樂，這就是徐總的性格）。
徐總經(jīng)常會問蹩腳的英文問路：“Can you help me?”。看著他那迷茫而又無助的眼神，熱心的你能幫幫他嗎？
請幫助他用最短的時間到達目的地（假設每一路公交車都只在起點站和終點站停，而且隨時都會開）。

Input 輸入數(shù)據(jù)有多組，每組的第一行是公交車的總數(shù)N(0<=N<=10000)；
第二行有徐總的所在地start，他的目的地end；
接著有n行，每行有站名s，站名e，以及從s到e的時間整數(shù)t(0<t<100)(每個地名是一個長度不超過30的字符串)。
note：一組數(shù)據(jù)中地名數(shù)不會超過150個。
如果N==-1，表示輸入結(jié)束。

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 50Hint: The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake雖然偶爾會迷路，但是因為有了你的幫助 **和**從此還是過上了幸福的生活。――全劇終―― 題目不難，主要是用字符串代替了編號，把字符串還原成編號就是簡單地最短路。 #include<stdio.h> #include<string.h> #define INF 1<<25 const int N = 160; int w[N][N], d[N], m; char add[N][40];void Init() {for(int i = 0; i <= 150; i++)for(int j = 0; j < 150; j++){if(i == j)w[i][j] = 0;elsew[i][j] = INF;} }int Change(char *s) {int i;for(i = 0; i < m; i++)if(strcmp(add[i], s) == 0)return i;if(i == m){strcpy(add[m], s);m++;return m-1;} }void Dijkstra() {int vis[N], i;memset(vis, 0, sizeof(vis));for(i = 0; i < m; i++)d[i] = INF;d[0] = 0;for(i = 0; i < m; i++){int x = 0, temp = INF;for(int y = 0; y < m; y++)if(!vis[y] && d[y] < temp)temp = d[x = y];if(temp == INF) break;vis[x] = 1;for(int y = 0; y < m; y++)if(d[y] > d[x] + w[x][y])d[y] = d[x] + w[x][y];} } int main() {int n, i, j;while(~scanf("%d",&n) && n != -1){Init();char st[40], ed[40], s1[40], s2[40];int a, b, c;scanf("%s%s",st, ed);strcpy(add[0], st);strcpy(add[1], ed);m = 2;for(i = 0; i < n; i++){scanf("%s%s%d",s1, s2, &c);a = Change(s1);b = Change(s2);w[a][b] = w[b][a] = c;}if(strcmp(st, ed) == 0){printf("0\n");continue;}Dijkstra();if(d[1] == INF)printf("-1\n");elseprintf("%d\n",d[1]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 2112 HDU Today 最短路（Dijkstra算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。