http://acm.hdu.edu.cn/showproblem.php?pid=2112

 

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

 

 

Source

ACM程序设计_期末考试（时间已定！！）

 

 

Recommend

lcy   |   We have carefully selected several similar problems for you:  2544 1874 1217 2680 1142 

 

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=50;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int n;
int edgenum;
int head[20005];
char ex[35],ey[35];
int vis[155];
int dis[155];

struct Edge
{
	int from,to,val,next;
}edge[20005];
void addedge(int u,int v,int w)
{
	Edge E={u,v,w,head[u]};
	edge[edgenum]=E;
	head[u]=edgenum++;
}
map<string,int>mp;
int t;

int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
	while(scanf("%d",&n)&&(n!=-1))
	{
		edgenum=0;
        memset(head,-1,sizeof(head));

        mp.clear();//一定要清零！
        getchar();
        scanf("%s%s",ex,ey);
        mp[ex]=1;
        t=2;
        if(!mp[ey])
        {
            mp[ey]=t++;
        }
        char a[35],b[35];
        int c;
        for(int i=1;i<=n;i++)
        {
            getchar();
            scanf("%s%s%d",a,b,&c);
            if(!mp[a])
            {
                mp[a]=t++;
            }
            if(!mp[b])
            {
                mp[b]=t++;
            }
            addedge(mp[a],mp[b],c);
            addedge(mp[b],mp[a],c);
        }
        queue<int>q;
        q.push(1);
        memset(vis,0,sizeof(vis));
        memset(dis,INF,sizeof(dis));
        vis[1]=1;
        dis[1]=0;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];i!=-1;i=edge[i].next)
            {
                int v=edge[i].to;
                if(dis[v]>dis[u]+edge[i].val)
                {
                    dis[v]=dis[u]+edge[i].val;
                    if(vis[v]==0)
                    {
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        }
        if(dis[mp[ey]]==INF)
            printf("-1\n");
        else
            printf("%d\n",dis[mp[ey]]);

	}
	return 0;
}

C++版本二

刚开始没有考虑起终点不在路径内的情况

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=50;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int n,m;
char s[N],t[N];
struct node {
    int e,w;
};
struct cmp{
    bool operator()(const node &a,const node &b){
            return a.w>b.w;
    }
};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    while(~scanf("%d",&n)&&n!=-1){
        scanf("%s%s",s,t);
        priority_queue<node,vector<node>,cmp>que;
        vector<node>v[200];
        int vis[200]={0};
        node x;
        map<string ,int >ma;
        char a[N],b[N];
        int c,cnt=0;
        if(!ma[s]){
            ma[s]=++cnt;
        }
        if(!ma[t]){
            ma[t]=++cnt;
        }
        for(int i=1;i<=n;i++){
            scanf("%s%s%d",a,b,&c);
            if(!ma[a]){
                ma[a]=++cnt;
            }
            if(!ma[b]){
                ma[b]=++cnt;
            }
            x.e=ma[b];
            x.w=c;
            v[ma[a]].push_back(x);
            x.e=ma[a];
            v[ma[b]].push_back(x);
        }
        x.e=ma[s];
        x.w=0;
        que.push(x);
        while(!que.empty()){
            x=que.top();
            que.pop();
            vis[x.e]=1;
            if(x.e==ma[t])
                break;
            for(int i=0,j=v[x.e].size();i<j;i++){
                node q;

                q.e=v[x.e][i].e;
                if(vis[q.e])
                    continue;
                q.w=x.w+v[x.e][i].w;
                que.push(q);
            }

        }
        if(x.e==ma[t])
            cout << x.w << endl;
        else
            cout << -1 << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}