【HDU - 2112 HDU Today】 最短路 dijkstra

D - HDU Today

經過錦囊相助，海東集團終于度過了危機，從此，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


雖然偶爾會迷路，但是因為有了你的幫助
**和**從此還是過上了幸福的生活。

――全劇終――      

題意：要從一個公交站前往另一個公交站，現在有n條路線連接配接兩個不同的公交站，問從指定的起點到終點需要的最小花費。

分析：也是一個裸的dijkstra，但是需要把字元串轉為相應的序号存起來，還有要注意的就是當起點終點相同時，最小花費為0。

然後，重點來了，本菜鳥第一次寫的不知道為什麼會WA，就把dijkstra函數小改了一下就A了，求大佬幫看下，多謝orz。

代碼如下：

WA代碼：

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long

using namespace std;
const int MX = 155;
const int INF = 1e9 + 5;

int n, num;
int dis[MX], vis[MX];
int mp[MX][MX];
char str[MX][35];

int change(char s[]){
    for(int i = 1; i <= num; i++){
        if(strcmp(s, str[i]) == 0){
            return i;
        }
    }
    strcpy(str[++num], s);
    return num;
}

void dijkstra(){
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    for(int i = 1; i <= num; i++){
        int k = -1, mindis = INF;
        for(int j = 1; j <= num; j++){
            if(!vis[j] && dis[j] < mindis){
                k = j;
                mindis = dis[j];
            }
        }
        vis[k] = 1;
        if(mindis == INF)   break;
        for(int j = 1; j <= num; j++){
            if(dis[j] > dis[k] + mp[k][j]){
                dis[j] = dis[k] + mp[k][j];
            }
        }
    }
    if(dis[2] == INF)   printf("-1\n");
    else printf("%d\n", dis[2]);
}

int main(){
    while(~scanf("%d", &n), n != -1){
        char s[35], e[35];
        for(int i = 1; i <= MX; i++){
            for(int j = 1; j <= MX; j++){
                if(i == j)  mp[i][j] = 0;
                else mp[i][j] = INF;
            }
        }
        scanf("%s%s", s, e);
        strcpy(str[1], s);
        strcpy(str[2], e);
        num = 2;
        for(int i = 1; i <= n; i++){
            int c;
            scanf("%s%s", s, e);
            scanf("%d", &c);
            int a = change(s);
            int b = change(e);
            mp[a][b] = mp[b][a] = c;
        }
        if(strcmp(str[1], str[2]) == 0){
            printf("0\n");
            continue;
        }
        dijkstra();
    }
    return 0;
}
           

AC代碼：

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long

using namespace std;
const int MX = 155;
const int INF = 1e9 + 5;

int n, num;
int dis[MX], vis[MX];
int mp[MX][MX];
char str[MX][35];

int change(char s[]){
    for(int i = 1; i <= num; i++){
        if(strcmp(s, str[i]) == 0){
            return i;
        }
    }
    strcpy(str[++num], s);
    return num;
}

void dijkstra(){
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= num; i++){
        dis[i] = mp[1][i];
    }
    vis[1] = 1;
    for(int i = 1; i <= num; i++){
        int k = -1, mindis = INF;
        for(int j = 1; j <= num; j++){
            if(!vis[j] && dis[j] < mindis){
                k = j;
                mindis = dis[j];
            }
        }
        vis[k] = 1;
        if(mindis == INF)   break;
        for(int j = 1; j <= num; j++){
            if(dis[j] > dis[k] + mp[k][j]){
                dis[j] = dis[k] + mp[k][j];
            }
        }
    }
    if(dis[2] == INF)   printf("-1\n");
    else printf("%d\n", dis[2]);
}

int main(){
    while(~scanf("%d", &n), n != -1){
        char s[35], e[35];
        for(int i = 1; i <= MX; i++){
            for(int j = 1; j <= MX; j++){
                if(i == j)  mp[i][j] = 0;
                else mp[i][j] = INF;
            }
        }
        scanf("%s%s", s, e);
        strcpy(str[1], s);
        strcpy(str[2], e);
        num = 2;
        for(int i = 1; i <= n; i++){
            int c;
            scanf("%s%s", s, e);
            scanf("%d", &c);
            int a = change(s);
            int b = change(e);
            mp[a][b] = mp[b][a] = c;
        }
        if(strcmp(str[1], str[2]) == 0){
            printf("0\n");
            continue;
        }
        dijkstra();
    }
    return 0;
}