2010 ACM-ICPC Multi-University Training Contest (7) - Host by HIT B Flight

时间：2010-08-20 来源：luyi0619

nlgn的最短路，需要讨论是否使用打折票。

Runid	Proid	Subtime	Judgestatus	Runtime	Memory	Language	Code Length	Author
505746	2945	2010-08-20 17:03:30	Accepted	5.99 s	41544 K	C++	2780 B	luyi0619

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<climits>
using namespace std;
map<string,int> mp;
char str1[100],str2[100];
bool flag[100001][2];
int len,inx,k1,k2,src,dst;
struct CITY
{
    int v,w;
        long long dis;
    bool flag;
    bool operator < (const CITY c) const
    {
        return dis>c.dis;
    }
};
CITY city,tmp;
vector<CITY> ivec[100001];
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)==2)
    {
        bool ok=false;
        memset(flag,0,sizeof(flag));
        mp.clear();
        for(int i=0; i<=n; i++)
            ivec[i].clear();
        inx=0;
        for(int i=0; i<m; i++)
        {
            scanf("%s %s %d",str1,str2,&len);
            if(mp.find(str1)==mp.end())
                mp[str1]=++inx;
            if(mp.find(str2)==mp.end())
                mp[str2]=++inx;
            k1=mp[str1];
            k2=mp[str2];
            city.v=k2;
            city.w=len;
            city.dis=0;
            city.flag=0;
            ivec[k1].push_back(city);
        }
        scanf("%s %s",str1,str2);
        if(mp.find(str1)==mp.end() || mp.find(str2)==mp.end())
        {
            printf("-1\n");
            continue;
        }
        src=mp[str1];
        dst=mp[str2];
        priority_queue<CITY> q;
        city.v=src;
        city.w=0;
        city.flag=0;
        city.dis=0;
        q.push(city);
        while(!q.empty())
        {
            city=q.top();
            q.pop();
            if(flag[city.v][city.flag])
                continue;
            flag[city.v][city.flag]=true;
            if(city.v==dst)
            {
                ok=true;
                break;
            }
            for(int i=0; i<ivec[city.v].size(); i++)
            {
                if(!city.flag)
                {
                    tmp.flag=1;
                    tmp.dis=city.dis+ivec[city.v][i].w/2;
                    tmp.v=ivec[city.v][i].v;
                    tmp.w=ivec[city.v][i].w;
                                        q.push(tmp);
                                        tmp.flag=0;
                    tmp.dis=city.dis+ivec[city.v][i].w;
                    tmp.v=ivec[city.v][i].v;
                    tmp.w=ivec[city.v][i].w;
                                        q.push(tmp);
                }
                                else
                                {
                                        tmp.flag=1;
                                        tmp.dis=city.dis+ivec[city.v][i].w;
                                        tmp.v=ivec[city.v][i].v;
                                        tmp.w=ivec[city.v][i].w;
                                        q.push(tmp);
                                }
            }
        }
        printf("%lld\n",ok==1?city.dis:-1);
    }
    return 0;
}