#https://github.com/shakayami/ACL-for-python/wiki/maxflow #最大フロー問題 from collections import deque class mf_graph: n=1 g=[[] for i in range(1)] pos=[] def __init__(self,N): """初期化:Kはグラフの頂点数です。 初期化した直後は、頂点数Kで辺0のグラフとなります。""" self.n=N self.g=[[] for i in range(N)] self.pos=[] def add_edge(self,From,To,cap): """辺の追加:uからvへ、最大容量c,流量0の辺を追加します。""" assert 0<=From and Fromtoという辺を持っている。 最大流量capの辺にflowだけ辺が流れている という意味となっています。 """ m=len(self.pos) result=[] for i in range(m): result.append(self.get_edge(i)) return result def change_edge(self,i,new_cap,new_flow): m=len(self.pos) assert 0<=i and i0): v=que.popleft() for e in self.g[v]: if e["cap"]==0 or level[e["to"]]>=0:continue level[e["to"]]=level[v]+1 if e["to"]==t:return que.append(e["to"]) def dfs(func,v,up): if (v==s):return up res=0 level_v=level[v] for i in range(Iter[v],len(self.g[v])): e=self.g[v][i] if (level_v<=level[e["to"]] or self.g[e["to"]][e["rev"]]["cap"]==0):continue d=func(func,e["to"],min(up-res,self.g[e["to"]][e["rev"]]["cap"])) if d<=0:continue self.g[v][i]["cap"]+=d self.g[e["to"]][e["rev"]]["cap"]-=d res+=d if res==up:return res level[v]=self.n return res flow=0 while(flow0): p=que.popleft() visited[p]=True for e in self.g[p]: if e["cap"] and not(visited[e["to"]]): visited[e["to"]]=True que.append(e["to"]) return visited INF = 10**9 n,m,d = list(map(int, input().split())) air = [] weit = [[] for _ in range(n)] X = [(0,0),(n-1,INF)] for _ in range(m): u,v,p,q,w = list(map(int, input().split())) u-=1 v-=1 q += d air.append((p,q,u,v,w)) X.append((u,p)) X.append((v,q)) weit[u].append(p) weit[v].append(q) weit[0].append(0) weit[n-1].append(INF) air.sort() Xdict = {x:i+1 for i,x in enumerate(sorted(list(set(X))))} mf = mf_graph(len(Xdict)+1) for i in range(m): p,q,u,v,w = air[i] mf.add_edge(Xdict[(u,p)],Xdict[(v,q)],w) for i in range(n): weit[i] = sorted(list(set(weit[i]))) if len(weit[i])<2:continue weit[i].sort() for j in range(len(weit[i])-1): mf.add_edge(Xdict[(i,weit[i][j])],Xdict[(i,weit[i][j+1])],INF) ans = mf.flow(Xdict[(0,0)],Xdict[(n-1,INF)]) print(ans)