hdu 2112 HDU Today(map与dijkstra的结合使用)  HDU Today Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6147    Accepted Submission(s): 1485 Problem Description 经过锦囊相助，海东集团最终度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候。XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，開始安度晚年了。 这样住了一段时间，徐总对当地的交通还是不太了解。有时非常郁闷。想去一个地方又不知道应该乘什么公交车。在什么地方转车。在什么地方下车（事实上徐总自己有车，却一定要与民同乐，这就是徐总的性格）。 徐总常常会问蹩脚的英文

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>

using namespace std;

map<string,int>mp;//映射
string s,e;//開始站和终点站
int n;

const int INF=10010100;

int m[160][160],d[160],used[160],k;

void dij()///dij模板
{
    fill(d,d+k+1,INF);//注意这里是k个，不是n个，n仅仅是路数,不是点数，一開始由于这个RE了好几次
    memset(used,0,sizeof(used));
    d[1]=0;
    while(1)
        {
            int v=-1;
            for(int u=1; u<=k; u++)
                if(!used[u]&&(v==-1||d[u]<d[v]))
                    v=u;
            if(v==-1)
                break;
            if(d[v]==INF)
                break;
            used[v]=1;
            for(int u=1; u<=k; u++)
                if(d[u]>d[v]+m[v][u])
                    d[u]=d[v]+m[v][u];
        }
}

int main()
{
    //int n;
    while(cin>>n)
        {
            if(n==-1)
                break;
            else
                {
                    mp.clear();
                    for(int i=0; i<=155; i++)//建图，初始化
                        for(int j=0; j<=155; j++)
                            {
                                if(i==j)
                                    m[i][j]=0;
                                else
                                    m[i][j]=INF;
                            }
                    int v;
                    k=1;
                    string s1,s2;
                    cin>>s>>e;
                    //用map映射给站名标记，起始站为1，终点站为2
                    mp[s]=k++;
                    mp[e]=k++;
                    for(int i=0; i<n; i++)
                        {
                            cin>>s1>>s2>>v;
                            if(!mp[s1])
                                mp[s1]=k++;
                            if(!mp[s2])
                                mp[s2]=k++;
                            if(v<m[mp[s1]][mp[s2]])
                                m[mp[s1]][mp[s2]]=m[mp[s2]][mp[s1]]=v;
                        }
                    //cout<<mp[e]<<endl;
                    if(s==e)
                        cout<<"0
";
                    else
                        {
                            dij();
                            if(d[2]==INF)
                                cout<<"-1
";
                            else
                                cout<<d[2]<<endl;
                        }
                }
        }
    return 0;
}