`

hdu 2066 一个人的旅行(起点到任意点的最短路)

阅读更多

一个人的旅行

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5994    Accepted Submission(s): 1995

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
            
         一道很简单的最短路,是求从起点到喜欢的点的最短路中的最短那个,spfa或者dijk都能求-从起点到任意点的最短距离,我用spfa搞定!
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 99999999;
const int N = 1005;

int map[N][N], dist[N], g[N];
bool visit[N];
int t, s, d;

void init()     //初始化函数
{
    int i, j;
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++)
            if(i == j) map[i][j] = 0;
            else map[i][j] = INF;
}

void input()    //输入函数
{
    int i, k, ti, tj, cost;
    while(t--)
    {
        scanf("%d %d %d", &ti, &tj, &cost); //输入两点距离
        if(cost < map[ti][tj])
            map[ti][tj] = map[tj][ti] = cost;
    }
    for(i = 0; i < s; i++)  //与家相邻的距离为0
    {
        scanf("%d", &k);
        map[0][k] = map[k][0] = 0;
    }
    for(i = 0; i < d; i++)  //输入想去的地方
        scanf("%d", &g[i]);
}

void spfa()     //spfa求起点到所有其它点的最短路
{
    int i, now;
    memset(visit, false, sizeof(visit));
    for(i = 0; i < N; i++) dist[i] = INF;
    dist[0] = 0;
    queue<int> Q;
    Q.push(0);
    visit[0] = true;
    while(!Q.empty())
    {
        now = Q.front();
        Q.pop();
        visit[now] = false;
        for(i = 0; i < N; i++)
        {
            if(dist[i] > dist[now] + map[now][i])
            {
                dist[i] = dist[now] + map[now][i];
                if(visit[i] == false)
                {
                    Q.push(i);
                    visit[i] = true;
                }
            }
        }
    }
}

int main()
{
    int i, MIN;
    while(scanf("%d %d %d", &t, &s, &d) != EOF)
    {
        init();
        input();
        spfa();
        MIN = INF;
        for(i = 0; i < d; i++)  //找所有想去的点中最短的
        {
            if(dist[g[i]] < MIN) MIN = dist[g[i]];
        }
        printf("%d\n", MIN);
    }

    return 0;
}
0
5
分享到:
评论

相关推荐

    最短路(HDU-2544).rar

    在有向或无向图G=(V,E)中,每条边e=(u,v)都关联一个非负权重w(e),最短路问题就是找出从源节点s到目标节点t的路径,使得这条路径上的边的权重之和最小。如果图中的权重代表距离,那么最短路就是实际意义上的最短路径...

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU最全ac代码

    通过学习和分析"HDU最全ac代码",你可以学到以下几个方面的知识: 1. **基础算法**:包括排序算法(快速排序、归并排序、堆排序等)、搜索算法(深度优先搜索、广度优先搜索、A*搜索等)、图论算法(最短路径、最小...

    HDU DP动态规划

    总的来说,"HDU DP动态规划"是一个关于使用动态规划解决HDU平台上某一题目的主题,它要求掌握动态规划的基本概念、方法,并能灵活应用到实际问题中,同时可能涉及到文件交互和调试,以完成问题的求解。

    hdu1250高精度加法

    具体地,题目涉及到了斐波那契数列的一个变种:F(1)=1, F(2)=1, F(3)=1, F(4)=1, F(n&gt;4)=F(n-1)+F(n-2)+F(n-3)+F(n-4),其中n &gt; 4。这里的关键是要能够计算出F(n)的值,而由于这个序列的增长速度非常快,传统的整数...

    HDU题目java实现

    HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案。这里的“java实现”意味着作者使用Java作为编程工具来解答这些算法题。 在Java编程方面,以下是一些可能涵盖的知识点: 1. ...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。...ACM HDU 题目分类是一个非常重要的参考资源,对于编程选手来说,掌握这些分类可以帮助他们更好地理解和解决问题。

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    ACM HDU

    【标签】"ACM题解 HDU"意味着这是一个关于如何解答HDU ACM题目的资源,可能包含了解题思路、算法解析、代码实现等方面的内容。这样的资料对于准备ACM比赛的选手或者希望提升算法能力的程序员来说非常有价值。 在...

    杭电ACMhdu1163

    【标签】:“杭电”代表题目来源于杭州电子科技大学,是ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest, ICPC)比赛的一个平台,提供了许多供学生练习和参赛的题目。"ACM"是此类竞赛的...

    hdu 的2072,2084,2082,1170,ac代码

    代码读取输入的整数`n`表示测试用例的数量,然后对每个测试用例,读取一个字符串`str`,并将它的后半部分移到前面,形成新的字符串`s`,最后输出结果。 3. HDU 2084 - 数组操作 这是一个涉及数组操作的问题。代码...

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    hdu1290解题报告

    题目背景设置在一个充满想象力的情境下,即如何通过不同数量的切刀将一个球形蛋糕分割成尽可能多的部分,以此激发读者的思考兴趣。 #### 题目描述 题目要求计算当在一个球体(本题中的蛋糕)上切割 _n_ 刀时(每一...

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    hdu acm2000至2099参考源码

    HDU ACM(ACM/ICPC国际大学生程序设计竞赛)是一个知名的编程竞赛平台,它提供了大量的算法题目供参赛者挑战。这些题目旨在提升参赛者的算法设计、编程和问题解决能力。"hdu acm2000至2099参考源码"是针对这个平台上...

    hdu2101解决方案

    hdu2101AC代码

    hdu动态规划算法集锦

    动态规划的关键在于确定状态转移方程,即如何从前一个或前几个状态转移到当前状态。 ### 知识点详解 #### Robberies (抢劫) 题目链接:[Robberies](http://acm.hdu.edu.cn/showproblem.php?pid=2955) - **问题...

Global site tag (gtag.js) - Google Analytics