http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1327. 飞行计划(王钦石)
时间限制:1.0s   内存限制:256.0MB  
总提交次数:247   AC次数:38   平均分:39.25
将本题分享到:
   
 
背景
  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<=105,0<=W<=2*105;输入保证答案不超出32位有符号整型。