一个人的旅行(HDOJ 2066)

文章目录[x]
  1. 1:Problem Description
  2. 2:Input
  3. 3:Output
  4. 4:Sample Input
  5. 5:Sample Output
  6. 6:My Code

Problem Description

虽然草儿是个路痴(就是在杭电待了一年多,居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行,因为在旅途中 会遇见很多人(白马王子,^0^),很多事,还能丰富自己的阅历,还可以看美丽的风景……草儿想去很多地方,她想要去东京铁塔看夜景,去威尼斯看电影,去阳明山上看海芋,去纽约纯粹看雪景,去巴黎喝咖啡写信,去北京探望孟姜女……眼看寒假就快到了,这么一大段时间,可不能浪费啊,一定要给自己好好的放个假,可是也不能荒废了训练啊,所以草儿决定在要在最短的时间去一个自己想去的地方!因为草儿的家在一个小镇上,没有火车经过,所以她只能去邻近的城市坐火车(好可怜啊~)。 

Input

输入数据有多组,每组的第一行是三个整数T,S和D,表示有T条路,和草儿家相邻的城市的有S个,草儿想去的地方有D个;
接着有T行,每行有三个整数a,b,time,表示a,b城市之间的车程是time小时;(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数,表示和草儿家相连的城市;
接着的第T+2行有D个数,表示草儿想去地方。 

Output

输出草儿能去某个喜欢的城市的最短时间。 

Sample Input

6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10

Sample Output

9 

My Code

这题关键就是增加一个起点的起点0,也就是草儿的家,草儿的家到普通起点的时间是0,这样就转换成了一个单源最短路,然后为了方便,同样增加一个终点的终点设成一个到不了的数就行了,我这里设了1005,然后只要输出0到1005的最短距离就是答案了。

这里有重边,稍微注意下。

#include <iostream>
#include <queue>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;

int T, S, D;
struct edge
{
    int w;
    int v;
    int next;
} e[1000000];                    //不知道有多少边就开的大了点
int tot;
int head[1000000];
int dis[1010];
bool vis[1010];
int s[1010];
int d[1010];
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<pair<int, int>> q;//first是到点的距离,second是点
    memset(dis, 0x3f, sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[0] = 0;
    q.push(make_pair(0, 0));        //将起点0入队,距离自然是0
    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 >> T >> S >> D)
    {
        tot=0;
        memset(head,0,sizeof(head));
        for (int i = 0; i < T; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            add(u, v, w);            //无向图,都存一遍
            add(v, u, w);
        }
        for (int i = 0; i < S; i++)
        {
            cin >> s[i];            //创造一个起点,使其变成单源最短路
            add(0, s[i], 0);
        }
        for (int i = 0; i < D; i++)
        {
            cin >> d[i];            //创造终点
            add(d[i], 1005, 0);
        }
        dijkstra();
        cout<<dis[1005]<<endl;
    }
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00