博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Hdu 2962 Trucking
阅读量:5263 次
发布时间:2019-06-14

本文共 1801 字,大约阅读时间需要 6 分钟。

题目大意:给你n个城市,m条道路,以及A城市与B城市之间隧道的限高,让你求最小路径。

 

思路:二分枚举所有的高度,然后通过Dijkstra算法求得最小的路径值。

注意:最后的mid不一定是正确的,需要用一个中间变量来保存。

我就这错了,于是去改SPFA,改建图,纠结了好久,最后发现是二分写错了。

 

这儿我花了两天的时间间断的找BUG,在师兄的提醒下终于找到了,我二分查找悲剧地写错了,放这提醒自己。

 

CODE:

 

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
using 
namespace std;
const 
int SIZE = 
10010;
const 
int INF = 
0xfffffff;
int u[
5*SIZE], v[
5*SIZE], w[
5*SIZE], next[
5*SIZE], h[
5*SIZE];
int first[SIZE], d[SIZE];
int n, m, cnt;
int s, e;
void read_graph(
int u1, 
int v1, 
int w1, 
int h1)
{
    u[cnt] = u1; v[cnt] = v1; w[cnt] = w1; h[cnt] = h1;
    next[cnt] = first[u[cnt]];
    first[u[cnt]] = cnt++;
}
int spfa(
int src, 
int mid)
{
    queue<
int> q;
    
bool inq[SIZE] = {
0};
    
for(
int i = 
1; i <= n; i++) d[i] = (i == src)?
0:INF;
    q.push(src);
    
while(!q.empty())
    {
        
int x = q.front(); q.pop();
        inq[x] = 
0;
        
for(
int e = first[x]; e!=-
1; e = next[e]) 
if(d[v[e]] > d[x]+w[e] && mid <= h[e])
        {
            d[v[e]] = d[x] + w[e];
            
if(!inq[v[e]])
            {
                inq[v[e]] = 
1;
                q.push(v[e]);
            }
        }
    }
    
if(d[e] == INF) 
return 
0;
        
return 
1;
}
void init()
{
    memset(first, -
1
sizeof(first));
    cnt = 
0;
}
int main()
{
    
int times = 
0;
    
while(~scanf(
"
%d%d
", &n, &m), n, m)
    {
        init();
        
while(m--)
        {
            
int u1, v1, w1, h1;
            scanf(
"
%d%d%d%d
", &u1, &v1, &h1, &w1);
            
if(h1 == -
1) h1 = INF;
            read_graph(u1, v1, w1, h1);
            read_graph(v1, u1, w1, h1);
        }
        
int x = 
0, y, ans = INF, mid, h;
        scanf(
"
%d%d%d
", &s, &e, &y);
        
while(x <= y)
        {
            mid = (x+y)>>
1;
            
if(spfa(s, mid))
            {
                x = mid+
1;
                ans = d[e];
                h = mid;          
//
保存mid 
            }
            
else y = mid-
1;
        }
        
if(times) printf(
"
\n
");
        printf(
"
Case %d:\n
", ++times);
        
if(ans != INF)
        {
            printf(
"
maximum height = %d\n
", h);
            printf(
"
length of shortest route = %d\n
", ans);
        }
        
else
        {
            printf(
"
cannot reach destination\n
");
        }
    }
}

 

 

 

转载于:https://www.cnblogs.com/g0feng/archive/2012/09/17/2688563.html

你可能感兴趣的文章
python 之 循环语句
查看>>
心得25--JDK新特性9-泛型1-加深介绍
查看>>
[转]ceph网络通信模块_以monitor模块为例
查看>>
HDOJ 1754 I Hate It(线段树基本操作)
查看>>
latex tree
查看>>
安装NVIDIA驱动时禁用自带nouveau驱动
查看>>
HDU-1255 覆盖的面积 (扫描线)
查看>>
css3学习01
查看>>
【USACO】 奶牛会展
查看>>
ActiveMQ笔记之点对点队列(Point-to-Point)
查看>>
继承和多态
查看>>
Dijkstra+计算几何 POJ 2502 Subway
查看>>
修复IE不能执行JS的方法
查看>>
程序员究竟该如何提高效率zt
查看>>
希尔排序法(缩小增量法)
查看>>
PHP编程基础学习(一)——数据类型
查看>>
MongoDB-JAVA-Driver 3.2版本常用代码全整理(2) - 查询
查看>>
NPOI处理Word文本中上下角标
查看>>
Android笔记 Handler
查看>>
如何阅读大型前端开源项目的源码(转)
查看>>