`

【枚举+最短路】HDU 2363 Cycling

阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=2363

题意:求最小高度差下的最短路

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL __int64
#define inf 0x3fffffff
#define M 105

struct xxx{
    int high;
    int low;
}x[10005];

struct son{
    int v;
    int w;
};

vector<son> g[M];
int dist[M], n, H[M];
bool inq[M];

bool cmp (xxx a, xxx b)
{
    return (a.high - a.low) < (b.high - b.low);
}

void spfa (int low, int high)
{
    int i, v, w, u = 1;
    for (i = 1; i <= n; i++)
    {
        dist[i] = inf;
        inq[i] = false;
    }
    queue<int> q;
    q.push (u);
    dist[u] = 0;
    inq[u] = true;
    while (!q.empty())
    {
        u = q.front();
        q.pop();
        inq[u] = false;
        if (H[u] < low || H[u] > high)    //起点也要限制
            continue;
        for (i = 0; i < g[u].size(); i++)
        {
            v = g[u][i].v;
            if (H[v] < low || H[v] > high)    //高度的限制
                continue;
            w = g[u][i].w;
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                if (!inq[v])
                {
                    q.push (v);
                    inq[v] = true;
                }
            }
        }
    }
}

int main()
{
    int t, m, u, v, w, i, j, k;
    son s;
    scanf ("%d", &t);
    while (t--)
    {
        scanf ("%d%d", &n, &m);
        for (i = 1; i <= n; i++)
        {
            scanf ("%d", H+i);
            g[i].clear();
        }
        k = 0;
        for (i = 1; i <= n; i++)
        {
            for (j = i; j <= n; j++)    //不能写成j=i+1,想想起点=终点的情况
            {
                x[k].low = min (H[i], H[j]);
                x[k++].high = max (H[i], H[j]);
            }
        }
        while (m--)
        {
            scanf ("%d%d%d", &u, &v, &w);
            s.v = v;
            s.w = w;
            g[u].push_back (s);
            s.v = u;
            g[v].push_back (s);
        }
        sort (x, x+k, cmp);        //按差排序
        for (i = 0; i < k; i++)    //差从小到大暴力枚举
        {
            spfa (x[i].low, x[i].high);
            if (dist[n] != inf)    //一旦可到达,立刻得出答案
                break;
        }
        printf ("%d %d\n", x[i].high-x[i].low, dist[n]);
    }
    return 0;
}
1
9
分享到:
评论
1 楼 panyanyany 2012-01-24  
靠,又不会做……本来想先求最小高度差的,可以求来求去求不了……

相关推荐

    acm入门之枚举搜索

    acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs

    最短路(HDU-2544).rar

    《最短路问题详解》 在计算机科学领域,最短路问题是一个经典的图论问题,其目标是寻找网络中两点间路径的最小成本。这个问题在众多应用中都有所体现,如交通规划、通信网络设计、社交网络分析等。在本篇内容中,...

    HDU刷题地图+精选详细笔记

    本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

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

    hdu.rar_hdu

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

    HDU最全ac代码

    "HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码集合,旨在帮助学习者理解和掌握各种算法,提升编程解决问题的能力。 首先,我们来了解一下ACM/ICPC比赛。这是一项全球性的编程竞赛,参赛...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    hdu 300+ AC 代码

    HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

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

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

    HDU+2000-2099+解题报告

    HDU(杭州电子科技大学)在线评测系统是许多编程竞赛爱好者和学习者经常访问的平台,它提供了大量的算法题目供用户练习和挑战。这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

Global site tag (gtag.js) - Google Analytics