| 题目名称 | 1794. [国家集训队2012]飞行计划 |
|---|---|
| 输入输出 | nt2012_route.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-11-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：4， 通过率：25% | ||||
 cstdio |
100 | 3.843 s | 3.93 MiB | C++ |
|
cstdio |
30 | 1.276 s | 0.90 MiB | C++ |
|
cstdio |
30 | 2.180 s | 3.63 MiB | C++ |
|
cstdio |
5 | 6.207 s | 0.90 MiB | C++ |
| 关于 飞行计划 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
所以呢……合法范围是[H-5,H+5]，一共是11个数而非10个……所以转化后分层图的节点数应该开到220000而非200000……否则后七个点会全部E掉……
E在这种地方也是醉了…… | ||||
飞行计划(王钦石)
时间限制：1.0s 内存限制：256.0MB
【背景】
1.wqs喜欢模拟飞行。
2.clj开了一家神犇航空，由于clj还要玩游戏，所以公司的事务由你来打理。
注意：题目中只是用了这样一个背景，并不与真实/模拟飞行相符
2.clj开了一家神犇航空，由于clj还要玩游戏，所以公司的事务由你来打理。
注意：题目中只是用了这样一个背景，并不与真实/模拟飞行相符
【问题描述】
神犇航空有一架航班从A地飞往B地，需要规划一条最经济的飞行线路。为了简化问题，我们认为地面是一个平面，高度为0，上有N个航路点，有M条双向航线，每条航线连接两个航路点，有两个参数H和W，表示以h高度通过这条航路，费用为(H-h)2+W。在每个航路点可以爬升/下降高度，每爬升一个高度需要费用C，而下降不需要费用。航路点0为A地，N-1为B地。
【输入格式】
第一行3个正整数，N,M和C，含义如题目所述；
以下M行，每行4个整数，u,v,H,W，表示u,v之间有一条航线，H,W为描述中的两个参数。
以下M行，每行4个整数，u,v,H,W，表示u,v之间有一条航线，H,W为描述中的两个参数。
【输出格式】
仅一行，一个整数，表示A地到B地的最小费用。
【样例输入】
3 2 5
0 1 10 10
1 2 20 10
0 1 10 10
1 2 20 10
【样例输出】
114
【数据规模和约定】
对于10%的数据，N,M<=5，H<=200；
另有20%的数据，N<=100，M<=500，H<=100；
对于全部的测试数据，N<=2000，M<=10000，C<=10，0<=u,v<N，0<=H<=105，0<=W<=2*105；输入保证答案不超出32位有符号整型。
另有20%的数据，N<=100，M<=500，H<=100；
对于全部的测试数据，N<=2000，M<=10000，C<=10，0<=u,v<N，0<=H<=105，0<=W<=2*105；输入保证答案不超出32位有符号整型。