use std::{cmp::Reverse, collections::BinaryHeap}; const INF: isize = 1isize << 60; #[derive(Debug, Clone, Copy)] struct MinCostFlowEdge { dest: usize, capacity: isize, cost: isize, rev: usize, } impl MinCostFlowEdge { fn new(dest: usize, capacity: isize, cost: isize, rev: usize) -> MinCostFlowEdge { MinCostFlowEdge { dest, capacity, cost, rev } } } struct MinCostFlow { paths: Vec>, potential: Vec, min_cost: Vec, prevv: Vec, preve: Vec, } /* 最小費用龍。 fの分だけ流すのにかかる最小のコスト */ impl MinCostFlow { fn new(n: usize) -> MinCostFlow { MinCostFlow { paths: vec![vec![]; n], potential: vec![0isize; n], min_cost: vec![0isize; n], prevv: vec![0usize; n], preve: vec![0usize; n], } } fn pusha2b(&mut self, a: usize, b: usize, capacity: isize, cost: isize) { let connecta = self.paths[a].len(); let connectb = self.paths[b].len(); self.paths[a].push(MinCostFlowEdge::new(b, capacity, cost, connectb)); self.paths[b].push(MinCostFlowEdge::new(a, 0, -cost, connecta)); } fn mincost_flow(&mut self, s: usize, t: usize, _f: isize) -> isize { let N = self.paths.len(); let mut ret = 0isize; let mut que = BinaryHeap::new(); self.potential = vec![0isize; N]; let mut f = _f; while f > 0 { self.min_cost = vec![INF; N]; que.push(Reverse((0, s))); self.min_cost[s] = 0; while let Some(Reverse((p, v))) = que.pop() { if self.min_cost[v] < p { continue; } for i in 0..self.paths[v].len() { let edge = self.paths[v][i]; let ncost = self.min_cost[v] + edge.cost + self.potential[v] - self.potential[edge.dest]; if edge.capacity > 0 && self.min_cost[edge.dest] > ncost { self.min_cost[edge.dest] = ncost; self.prevv[edge.dest] = v; self.preve[edge.dest] = i; que.push(Reverse((self.min_cost[edge.dest], edge.dest))); } } } if self.min_cost[t] == INF { return -1; } for i in 0..N { self.potential[i] += self.min_cost[i]; } let mut d = f; let mut temp = t; while temp != s { d = d.min(self.paths[self.prevv[temp]][self.preve[temp]].capacity); temp = self.prevv[temp]; } f -= d; ret += d * self.potential[t]; temp = t; while temp != s { let edge = self.paths[self.prevv[temp]][self.preve[temp]]; self.paths[self.prevv[temp]][self.preve[temp]].capacity -= d; self.paths[temp][edge.rev].capacity += d; temp = self.prevv[temp]; } } ret } } fn main() { let mut nm = String::new(); std::io::stdin().read_line(&mut nm).ok(); let nm: Vec = nm.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nm[0]; let m = nm[1]; let mut flow = MinCostFlow::new(n); for _ in 0..m { let mut temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); let temp: Vec = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let u = temp[0]-1; let v = temp[1]-1; let c = temp[2] as isize; let d = temp[3] as isize; flow.pusha2b(u, v, 1, c); flow.pusha2b(u, v, 1, d); flow.pusha2b(v, u, 1, c); flow.pusha2b(v, u, 1, d); } println!("{}", flow.mincost_flow(0, n-1, 2)); }