6695: BZOJ2695：飞行计划

Memory Limit：128 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

1.wqs喜欢模拟飞行。
　　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为描述中的两个参数。

输出格式

　　仅一行，一个整数，表示A地到B地的最小费用。

样例输入

3 2 5
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<=10^5，0<=W<=2*10^5；输入保证答案不超出32位有符号整型。

题目来源

没有写明来源

加入题单

上一题 下一题 算法标签：