F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 3948. -- 触电的王胖浩

3948: 触电的王胖浩

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 121  Solved: 23
[Submit][Status][Discuss]

Description

王胖浩触电了!快来救他!现在有m条电线,n个交叉点。每条电线连接两个交叉点。电源在s点,王胖浩在t点。每
条线段有硬度,宽度,危险程度。求确定剪断那些电线,使得s与t不连通,且最小化要剪断的电线的硬度之和与宽
度之和与危险程度之和的乘积。请在2s以内出解,否则王胖浩就被电死了。

Input

本题有多组数据,以EOF结尾。第一行4个数n,m,s,t (s不等于t) ,如题面所述。接下来m行每行5个数,xi,yi,hi,
wi,di,分别表示第i条电线连接的两个交叉点,硬度,宽度和危险程度。

Output

每组数据占一行输出,每行一个数ans,表示最小的解。

Sample Input

4 4 1 4
1 2 1 1 1
1 3 1 2 1
3 4 2 1 1
2 4 2 2 2

Sample Output

12

HINT

100%:n<=50,m<=100,hi,wi,di<=10000

数据组数不会超过2组

Source

2014年国家集训队十五人互测

[Submit][Status][Discuss]

HOME Back