HDU Today（HDOJ 2112）

2020-01-23 431次阅读 0条评论 2人点赞

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


虽然偶尔会迷路，但是因为有了你的帮助
**和**从此还是过上了幸福的生活。

――全剧终――

My Code

#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
using namespace std;

int n;
string S, E;
struct edge
{
    int w;
    int v;
    int next;
} e[20005];
int tot;
int cnt;
int head[20005];
int dis[200];
bool vis[200];
map StoI;          //通过map将地名编号，转化成int
void add(int u, int v, int w)
{
    e[++tot].v = v;
    e[tot].w = w;
    e[tot].next = head[u];
    head[u] = tot;
}
void dijkstra()     //dijkstra堆优化
{
    priority_queue> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[StoI[S]] = 0;
    q.push(make_pair(0, StoI[S]));
    while (q.size())
    {
        int p = q.top().second;
        q.pop();
        if (vis[p])
            continue;
        vis[p] = 1;
        for (int i = head[p]; i != 0; i = e[i].next)
        {
            if (dis[e[i].v] > dis[p] + e[i].w)
            {
                dis[e[i].v] = dis[p] + e[i].w;
                q.push(make_pair(-dis[e[i].v], e[i].v));
            }
        }
    }
}
int main()
{
    while (cin >> n && n != -1)
    {
        tot = 0;
        cnt = 0;
        memset(head, 0, sizeof(head));
        StoI.clear();           //记得清空
        cin >> S >> E;
        StoI[S] = ++cnt;
        if (!StoI.count(E))     //起点终点可能相等
            StoI[E] = ++cnt;
        for (int i = 0; i < n; i++)
        {
            string u, v;
            int w;
            cin >> u >> v >> w;
            if (!StoI.count(u))
                StoI[u] = ++cnt;
            if (!StoI.count(v))
                StoI[v] = ++cnt;
            add(StoI[u], StoI[v], w);
            add(StoI[v], StoI[u], w);
        }
        dijkstra();
        if (dis[StoI[E]] == inf)        //最后有可能到不了，输出-1
            cout << -1 << endl;
        else
            cout << dis[StoI[E]] << endl;
    }
    return 0;
}