#P3948. 触电的王胖浩

    ID: 3154 传统题 2000ms 512MiB 尝试: 127 已通过: 5 难度: 9 上传者: 标签>CF2800搜索网络流回溯法图论2014年国家集训队十五人互测

触电的王胖浩

题目描述

王胖浩触电了!快来救他!

现在有 mm 条电线,nn 个交叉点。每条电线连接两个交叉点。电源在 ss 点,王胖浩在 tt 点。每条线段有硬度,宽度,危险程度。

求确定剪断那些电线,使得 ss 与 tt 不连通,且最小化要剪断的电线的硬度之和与宽度之和与危险程度之和的乘积。

请在 2s 以内出解,否则王胖浩就被电死了。

输入格式

本题有多组数据,以 EOF 结尾。

第一行 44 个数 n,m,s,tn,m,s,t,如题面所述。

接下来 mm 行,每行 55 个数 xi,yi,hi,wi,dix_i,y_i,h_i,w_i,d_i,分别表示第 ii 条电线连接的两个交叉点,硬度,宽度和危险程度。

输出格式

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

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

数据范围与提示

对于 100%100\% 的数据,1≤n≤501\le n\le 50,1≤m≤1001\le m\le 100,0≤hi,wi,di≤1040\le h_i,w_i,d_i\le 10^4,s≠ts\ne t,数据组数不会超过 22 组。

题目来源

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