hdu2112 dijkstra算法+堆优化

以你之姓@ 2022-08-03 00:17 175阅读 0赞

# HDU Today #

**Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 18688    Accepted Submission(s): 4412**

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
    
    
    虽然偶尔会迷路，但是因为有了你的帮助
    **和**从此还是过上了幸福的生活。
    
    ――全剧终――

Author

lgx

最短路问题，以前做的都是用数字表示的顶点，现在使用字符串表示的顶点，用map把字符串转化成数字，然后在dijkstra就行啦。注意起始地跟目的地一样的地方。

//hdu2112
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    struct st
    {
        int to,cost;
        st(int a,int b)
        {
            to=a;
            cost=b;
        }
    };
    int cnt;
    map<string,int> mp;
    int d[155];
    vector<st> v[155];
    priority_queue<pii,vector<pii>,greater<pii> > q;//声明优先队列
    
    int getNum(string & s)
    {
        if(mp.find(s)!=mp.end())return mp[s];
        return mp[s]=++cnt;
    }
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
    
            if(n==-1)break;
            for(int i=0;i<=150;i++)v[i].clear();//清空
            mp.clear();
            string start,finally;
            cin>>start>>finally;
            mp[start]=1;         //起始地设置为1
            mp[finally]=2;         //目的地设置为2
            cnt=2;
            string t1,t2;
            int c;
            for(int i=0;i<n;i++)
            {
                cin>>t1>>t2;
                c=in();
                int x=getNum(t1);     //转换成数字
                int y=getNum(t2);
                v[x].push_back(st(y,c));
                v[y].push_back(st(x,c));//公交车可以往回开。。也就是说是无向图。。
    
            }
            if(start==finally)//注意这个地方，没有就WA，因为起始地跟目的地设置的数字不同
            {
                puts("0");
                continue;
            }
            mem(d,inf);
            d[1]=0;
            q.push(pii(0,1));
            while(!q.empty())
            {
                pii now = q.top();
                q.pop();
                int t=now.second;
                if(d[t]<now.first)continue;             //别漏了，当前距离不能被更新
                for(int i=0;i<(int)v[t].size();i++)
                {
                    st tmp=v[t][i];
                    if(d[tmp.to]>d[t]+tmp.cost)
                    {
                        d[tmp.to]=d[t]+tmp.cost;
                        q.push(pii(d[tmp.to],tmp.to));
                    }
                }
            }
            if(d[2]==inf)puts("-1");
            else printf("%d\n",d[2]);
        }
        return 0;
    }