HDU Today

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 51562 Accepted Submission(s): 12238

Problem Description

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

Input

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

Output

如果徐總能到達(dá)目的地，輸出最短的時(shí)間；否則，輸出“-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

代碼：

#include<stdio.h> 
#include<iostream> 
#include<map> 
#include<queue> 
using namespace std; 
#define INF 99999999 
int Map[155][155],n,node[155]; 
void init() 
{ 
    for(int i=0;i<=150;i++) 
        for(int j=i;j<=150;j++) 
            Map[i][j]=Map[j][i]=node[i]=INF; 
} 
 
void spfa(int star) 
{ 
    int inQ[155]={0}; 
    queue<int>Q; 
    inQ[star]=1; Q.push(star); 
    node[star]=0; 
    while(!Q.empty()) 
    { 
        star=Q.front();
        Q.pop(); 
        inQ[star]=0; 
        for(int i=1;i<=n;i++) 
            if(Map[star][i]+node[star]<node[i]) 
            { 
                node[i]=Map[star][i]+node[star]; 
                if(!inQ[i]) 
                    Q.push(i),inQ[i]=1; 
            } 
    } 
} 
 
int main() 
{ 
    int star,end,m,a,b,p; 
    char aa[35],bb[35]; 
    map<string,int>loc; 
    while(scanf("%d",&m)>0&&m!=-1) 
    { 
        init(); n=1; loc.clear(); 
        scanf("%s%s",aa,bb); 
        loc[aa]=n; star=n; 
        if(!loc[bb]){n++;loc[bb]=n;} 
         end=loc[bb]; 
        while(m--) 
        { 
            scanf("%s%s%d",aa,bb,&p); 
            if(!loc[aa])
            {
                n++;
                loc[aa]=n;
            }
            a=loc[aa]; 
            if(!loc[bb])
            {
                n++;
                loc[bb]=n;
            }
            b=loc[bb]; 
            if(Map[a][b]>p) 
                Map[a][b]=Map[b][a]=p; 
        } 
        if(star==end) 
        { 
            printf("0\n");
            continue; 
        }
        spfa(star); 
        if(node[end]==INF)
            node[end]=-1; 
        printf("%d\n",node[end]); 
    } 
}

hdu 2112 HDU Today

HDU Today