`
huyifan951124
  • 浏览: 82779 次
社区版块
存档分类
最新评论

hdu2962 最短路

 
阅读更多

题目大意:就是给定起始点和结束点以及卡车的重量,问你在保证卡车重量最大的前提下,最短路径是多少,我们可以枚举卡车的重量,在对每个卡车的重量进行dijkstra,算到终点是否存在最短路径。当然枚举也可以用二分进行优化,时间差的还是蛮多的。

             
  2016-08-05 15:23:00 Accepted 2962 9297MS 9500K 2257 B G++  

 

   2016-08-05 15:34:54 Accepted 2962 1606MS 9496K 2516 B G++  

下面那个是进行过二分优化的。

//二分+dijkstra
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
int n,m,ch,h,l,c,r,s,e,ans1,ans2;
bool visited[1005];
int a[1005][1005],height[1005][1005];
int dist[1005];
int hei[1005];
void dijkstra(int he)
{
    memset(visited,false,sizeof(visited));
    memset(dist,0x3f,sizeof(dist));
    visited[s]=true;
    for(int i=1;i<=n;i++)
    {
        hei[i]=height[s][i];
        if(hei[i]<he)
            dist[i]=INF;
        else
            dist[i]=a[s][i];

    }
    for(int i=1;i<=n;i++)
    {
        int MIN=INF,node=-1;
        for(int j=1;j<=n;j++)
        {
            if(!visited[j]&&dist[j]<MIN&&hei[j]>=he)
            {
                MIN=dist[j];
                node=j;
            }
        }

        if(node==-1)
            return;
        visited[node]=true;

        for(int j=1;j<=n;j++)
        {
            if(!visited[j]&&height[node][j]>=he&&dist[j]>dist[node]+a[node][j])
            {
                dist[j]=dist[node]+a[node][j];
                hei[j]=height[node][j];
            }
        }

    }

}
int main()
{
    int sym=0;
    while(true)
    {
        sym++;
        ans1=-1;
        ans2=-1;
        memset(a,0x3f,sizeof(a));
        memset(height,0,sizeof(height));
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)
            break;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&l,&r,&h,&c);
            a[l][r]=a[r][l]=c;
            if(h==-1)
                height[l][r]=height[r][l]=INF;
            else
                 height[l][r]=height[r][l]=h;
        }
        for(int i=1;i<=n;i++)
        {
            a[i][i]=height[i][i]=0;
        }
        scanf("%d%d%d",&s,&e,&ch);
        int left=1;
        int right=ch;
       int mid=0;
        while(left<=right)
        {
            mid=(left+right)/2;
            dijkstra(mid);
            if(dist[e]!=INF)
            {
                ans1=dist[e];
                ans2=mid;
                left=mid+1;
            }
            else
                right=mid-1;
        }
        if(sym!=1)
            printf("\n");
        printf("Case %d:\n",sym);
        if(ans1==-1&&ans2==-1)
        {
            printf("cannot reach destination\n");
        }
        else
        {
            printf("maximum height = %d\n",ans2);
            printf("length of shortest route = %d\n",ans1);
        }

    }
    return 0;
}




//枚举+dijkstra
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
int n,m,ch,h,l,c,r,s,e;
bool visited[1005];
int a[1005][1005],height[1005][1005];
int dist[1005];
int hei[1005];
void dijkstra(int he)
{
    memset(visited,false,sizeof(visited));
    memset(dist,0x3f,sizeof(dist));
    visited[s]=true;
    for(int i=1;i<=n;i++)
    {
        hei[i]=height[s][i];
        if(hei[i]<he)
            dist[i]=INF;
        else
            dist[i]=a[s][i];

    }
    for(int i=1;i<=n;i++)
    {
        int MIN=INF,node=-1;
        for(int j=1;j<=n;j++)
        {
            if(!visited[j]&&dist[j]<MIN&&hei[j]>=he)
            {
                MIN=dist[j];
                node=j;
            }
        }

        if(node==-1)
            return;
        visited[node]=true;

        for(int j=1;j<=n;j++)
        {
            if(!visited[j]&&height[node][j]>=he&&dist[j]>dist[node]+a[node][j])
            {
                dist[j]=dist[node]+a[node][j];
                hei[j]=height[node][j];
            }
        }

    }

}
int main()
{
    int sym=0;
    while(true)
    {
        sym++;
        memset(a,0x3f,sizeof(a));
        memset(height,0,sizeof(height));
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)
            break;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&l,&r,&h,&c);
            a[l][r]=a[r][l]=c;
            if(h==-1)
                height[l][r]=height[r][l]=INF;
            else
                 height[l][r]=height[r][l]=h;
        }
        for(int i=1;i<=n;i++)
        {
            a[i][i]=height[i][i]=0;
        }
        scanf("%d%d%d",&s,&e,&ch);
        while(ch!=0)
        {

            dijkstra(ch);
            if(dist[e]!=INF)
            {
                break;
            }
            ch--;
        }
        if(sym!=1)
            printf("\n");
        printf("Case %d:\n",sym);
        if(ch==0)
        {
            printf("cannot reach destination\n");
        }
        else
        {
            printf("maximum height = %d\n",ch);
            printf("length of shortest route = %d\n",dist[e]);
        }

    }
    return 0;
}



 

分享到:
评论

相关推荐

    最短路(HDU-2544).rar

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

    HDU最全ac代码

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

    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题目java实现

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

    ACM HDU题目分类

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

    hdu1250高精度加法

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

    HDU DP动态规划

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

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

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

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

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    ACM HDU

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

    hdu2101解决方案

    hdu2101AC代码

    杭电ACMhdu1163

    8. **C++编程**:虽然现在ACM竞赛支持多种编程语言,但C++是最常用的语言,其模板、STL库(容器、算法)等特性在解决ACM问题中非常实用。 9. **调试技巧**:学会使用调试工具(如gdb),理解并处理运行时错误(如段...

    Hdu1000—2169部分代码

    3. **动态规划**:解决具有重叠子问题和最优子结构的问题。 4. **图论算法**:最短路径算法(Dijkstra、Floyd-Warshall)、拓扑排序、最小生成树(Prim、Kruskal)等。 5. **数学方法**:模运算、数论、组合数学等。...

    hdu 5007 Post Robot

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

    HDU acm-PPT课件

    在ACM竞赛中,C++是最常用的语言,因其高效、灵活和丰富的库支持而备受青睐。学习C++的基本语法,包括变量、数据类型、控制结构、函数等,是首要任务。同时,理解算法基础如排序(冒泡、选择、插入、快速、归并等)...

    hdu acm1166线段树

    hdu 1166线段树代码

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

    这些代码是针对HDU(杭州电子科技大学在线评测系统)的四道编程题目提交的AC(Accepted)解决方案。每段代码对应一个不同的问题,下面是每个问题的简要说明及代码解析: 1. HDU 2072 - 字符串处理 这个问题涉及到...

Global site tag (gtag.js) - Google Analytics