Trucking
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2216 Accepted Submission(s): 757
For the given cargo truck, maximizing the height of the goods transported is equivalent to maximizing the amount of goods transported. For safety reasons, there is a certain height limit for the cargo truck which cannot be exceeded.
1 2 7 5
1 3 4 2
2 4 -1 10
2 5 2 4
3 4 10 1
4 5 8 5
1 5 10
5 6
1 2 7 5
1 3 4 2
2 4 -1 10
2 5 2 4
3 4 10 1
4 5 8 5
1 5 4
3 1
1 2 -1 100
1 3 10
0 0
0 0
Case 1:
maximum height = 7
length of shortest route = 20
Case 2:
maximum height = 4
length of shortest route = 8
Case 3:
cannot reach destination
题意:给定一个无向图,每条边有长度,通过最大高度两个权值,求解从起点到终点的能通过的最大高度以及在此高度上的最短路径长度
思路:二分搜索,每次进行一次最短路算法Dijkstra,路径更新公式需要添加 map[i][v].h>=p||map[i][v].h==-1
需要注意最后一行不能输出\n PE了两次
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define Max 1005
#define INF 9999999
struct node
{
int len,h;
}map[Max][Max];
bool vis[Max];
int dis[Max];
int c,r;
int s,e,height; bool Dijkstra(int p)
{
int i,j;
memset(vis,,sizeof(vis));
for(i=;i<=c;i++)
dis[i]=INF;
dis[s]=;
while(true)
{
int v=;
for(i=;i<=c;i++)
{
if(!vis[i]&&(v==||dis[i]<dis[v]))
v=i;
}
if(v==)
break;
vis[v]=;
//cout<<v<<endl;
// cout<<"3 "<<dis[3]<<endl;
for(i=;i<=c;i++)
{
if(vis[i]==&&(map[i][v].h>=p||map[i][v].h==-)&&(dis[v]+map[i][v].len<dis[i]))
dis[i]=dis[v]+map[i][v].len;
}
}
return dis[e]!=INF;
} int main()
{
int i,j;
int a,b;
int t=;
freopen("in.txt","r",stdin);
while(scanf("%d%d",&c,&r))
{
if(c==&&r==)
break;
for(i=;i<=c;i++)
for(j=;j<=c;j++)
{
map[i][j].h=;
map[i][j].len=INF;
}
for(i=;i<r;i++)
{
scanf("%d%d",&a,&b);
scanf("%d%d",&map[a][b].h,&map[a][b].len);
map[b][a].h=map[a][b].h;
map[b][a].len=map[a][b].len;
}
scanf("%d%d%d",&s,&e,&height);
int lb=,rb=height+,mid,ans,length=INF;
while(rb-lb>)
{
mid=(rb+lb)/;
if(Dijkstra(mid))
{
length=dis[e];
ans=mid;
lb=mid;
}
else
rb=mid;
}
if(t!=)
printf("\n");
if(length==INF)
printf("Case %d:\ncannot reach destination\n",t++);
else
{
printf("Case %d:\n",t++);
printf("maximum height = %d\n",ans);
printf("length of shortest route = %d\n",length);
}
}
}
Trucking(HDU 2962 最短路+二分搜索)的更多相关文章
-
Day4 - I - Trucking HDU - 2962
A certain local trucking company would like to transport some goods on a cargo truck from one place ...
-
hdu 2962 最短路+二分
题意:最短路上有一条高度限制,给起点和最大高度,求满足高度最大情况下,最短路的距离 不明白为什么枚举所有高度就不对 #include<cstdio> #include<cstring ...
-
ACM: HDU 2544 最短路-Dijkstra算法
HDU 2544最短路 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Descrip ...
-
UESTC 30 &;&;HDU 2544最短路【Floyd求解裸题】
最短路 Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submiss ...
-
hdu 5521 最短路
Meeting Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total ...
-
HDU - 2544最短路 (dijkstra算法)
HDU - 2544最短路 Description 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt.但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以 ...
-
hdu 2962 Trucking (二分+最短路Spfa)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2962 Trucking Time Limit: 20000/10000 MS (Java/Others ...
-
hdu 2962 Trucking (最短路径)
Trucking Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total ...
-
HDU - 2962 Trucking SPFA+二分
Trucking A certain local trucking company would like to transport some goods on a cargo truck from o ...
随机推荐
-
移植SlidingMenu Android library,和安装example出现的问题解决
很多项目都用到类似左侧滑动菜单的效果,比如facebook,evernote,VLC for android等等,这很酷 源代码可以从GitHub的https://github.com/jfeinst ...
-
JS兼容所有浏览器的一段加入收藏代码,设置为首页
<script language="javascript" type="text/javascript"> function addfavorite ...
-
C#输出log信息
在写程序的过程中,有时候我们需要添加一些log信息,这个时候,可以采用下面的方法来实现. public static void WriteLog(string ExtraMsg, Exception ...
-
javaScript与MVC
MVC,就是Module,View,Controller分离,使业务逻辑更加清晰,但是现在公司的项目中很多地方那个不是这样的,很多业务逻辑放在了javascript中实现,这样做的优点就是对于技术要求 ...
-
【转】int const A::func()和int A::func() const
int const A::func() { return 0; }int A::func() const { return 0; } 上面的代码是合法的,其中A::func成员函数[只能在成员函数后面 ...
-
Android OpenGL ES(十二):三维坐标系及坐标变换初步 .
OpenGL ES图形库最终的结果是在二维平面上显示3D物体(常称作模型Model)这是因为目前的打部分显示器还只能显示二维图形.但我们在构造3D模型时必须要有空间现象能力,所有对模型的描述还是使用三 ...
-
指针--摘自C++技术网 作者dx
“指针是什么?”“指针就是一种数据类型.”“你确定?”“那数据类型是什么?额,这个???类型就是类型,还能怎么解释嘛.”“指针有多少种?”“指针有好多种,比如整型指针,字符指针等等.”“指针是怎么确定 ...
-
1分钟选好最合适你的JavaScript框架
欢迎大家持续关注葡萄城控件技术团队博客,更多更好的原创文章尽在这里~~ Javascript框架(以下简称框架)也被称为Javascript库,是一组包含丰富功能和函数的JavaScript代码集, ...
-
#YCB#待做题目与填坑资料
各种填坑资料(qwq) 主席树(by YL)戳 树套树(by ZSY)戳 不要问我这些题咋来的(查大佬的水表呗) 题目列表: [HDU5977]Garden of Eden [BZOJ2752][HA ...
-
ubuntu 16.04 源代码安装libusb
libusb是一个跨平台的usb通讯库:https://libusb.info/ 在ubuntu16上安装 1. 首先安装 libudev-dev sudo apt-get install libud ...