#https://yukicoder.me/problems/no/654 #before start, after all gather edge must be processed in some problems from collections import deque inpPh = 5 debug = True debug = False if not debug: inpPh = 0 input1 =''' 2 2 5 1 2 0 25 10 1 2 10 40 5 '''[1:] input2 =''' 4 5 5 1 2 0 15 40 1 3 5 20 10 2 3 30 40 20 2 4 50 80 20 3 4 50 70 30 '''[1:] input3 =''' 3 4 5 1 2 0 10 10 1 2 10 20 3 2 3 15 25 2 2 3 5 15 10 '''[1:] input4 =''' 4 3 5 1 2 0 10 100 2 3 15 31 100 3 4 35 45 100 '''[1:] input5 =''' 4 40 9 2 3 90 99 43 2 3 12 60 56 1 3 5 9 30 4 3 76 96 88 2 4 76 86 66 1 2 36 91 5 2 1 23 82 87 1 4 66 83 12 1 2 2 33 72 4 1 2 90 30 3 2 32 84 25 4 2 13 99 56 4 3 49 56 94 1 3 29 42 31 1 2 86 88 93 3 4 43 51 28 3 4 5 69 60 3 1 3 4 39 1 4 7 73 99 3 2 31 85 94 1 2 89 94 94 2 1 34 70 62 3 4 39 94 63 4 1 23 30 96 3 4 41 81 29 4 3 57 62 48 3 2 33 54 27 3 1 44 73 44 3 2 50 70 19 4 2 19 36 82 4 2 95 97 94 3 4 20 58 10 1 4 4 97 33 2 3 46 58 58 3 1 0 80 45 4 1 1 76 43 3 2 16 97 9 3 1 13 16 45 2 4 4 16 12 2 3 68 98 12 '''[1:] output1_2_3_4_5 = ''' 15 50 2 0 240 ''' inputXs = [input1, input2, input3, input4, input5, None] try: inputA0 except: inputXs[-1] = inputXs[0] else: inputXs[-1] = inputA0 inploc = inpPh - 1 #0,1,2 if debug and inpPh > 0: #print('selected_input:\n'+inputXs[inploc]) pass inpX_lst = [] if inpPh > 0: inpX_lst = inputXs[inploc].splitlines() if inpPh == 0: N,M,d = tuple(map(lambda x: int(x), input().split() ) ) else: N,M,d = tuple( map(lambda x: int(x), inpX_lst.pop(0).split() ) ) V, E = N, M INF = float('inf') s, t = 0, V-1 time_seq = [[] for _ in range(N)] nelist,celist = [],[] elist = [] nov_cur = V for i in range(E): if inpPh == 0: u,v,p,q,w = tuple(map(lambda x: int(x), input().split() )) else: u,v,p,q,w = tuple(map(lambda x: int(x), inpX_lst.pop(0).split() )) u, v, q = u-1,v-1,q+d timed_u, timed_v = nov_cur, nov_cur +1 ne = {'id':i,'u':timed_u, 'v':timed_v, 'ouv':(u,v), 'c':w, 'f':0, 'p':p, 'q':q, 'rev':None} nov_cur += 2 nelist.append(ne) #test = {'time':p,'prcd':1,'jnt':'u','e':ne} time_seq[u].append((p,1,'u',ne)) time_seq[v].append((q,0,'v',ne)) #print(ne) #print(u,v,p,q,w) for i in range(N): time_seq[i] = sorted(time_seq[i], key=lambda x: (x[0],x[1]) ) #print('time_seq') for i in range(N): break print(f'#town({i}):') for e in time_seq[i]: print(e) #print() V = nov_cur #print(time_seq[s]) clock0,uv_pri0,junc_ent0,e0 = s_fst = time_seq[s][0] clock1,uv_pri1,junc_ent1,e1 = t_last = time_seq[t][-1] from_s = e0[junc_ent0] to_t = e1[junc_ent1] ne0 = ne = {'id':len(nelist)+0, 'u':s, 'v':from_s, 'ouv':(s,s), 'c':INF, 'f':0, 'p':None, 'q':None, 'rev':None} ne1 = ne = {'id':len(nelist)+1, 'u':to_t, 'v':t, 'ouv':(t,t), 'c':INF, 'f':0, 'p':None, 'q':None, 'rev':None} nelist.append(ne0) nelist.append(ne1) for i in range(N): while len( time_seq[i] ) > 0 : break clock,uv_pri,junc_ent,e = time_seq[i][0] if junc_ent == 'v': break else: time_seq[i].pop(0) while len(time_seq[i]) > 0: break clock,uv_pri,junc_ent,e = time_seq[i][-1] if junc_ent == 'u': break else: time_seq[i].pop(-1) for j in range(1, len(time_seq[i]) ): clock0,uv_pri0,junc_ent0,e0 = time_seq[i][j-1] clock1,uv_pri1,junc_ent1,e1 = time_seq[i][j] if clock0 == clock1: e1[junc_ent1] = e0[junc_ent0] continue else: new_u, new_v= e0[junc_ent0] ,e1[junc_ent1] ne = {'id':len(nelist),'u':new_u, 'v':new_v, 'ouv':(i,i),'c':INF, 'f':0, 'p':None, 'q':None,'rev':None} nelist.append(ne) E = len(nelist) for ne in nelist: ne_id, u, v, = ne['id'],ne['u'], ne['v'] ne['rev'] = E + ne_id ouv = (ne['ouv'][1], ne['ouv'][0]) ce = {'id':E + ne_id, 'u':v, 'v':u, 'ouv':ouv, 'c':0, 'f':0, 'p':None, 'q':None, 'w':0, 'rev':ne_id} celist.append(ce) elist = nelist + celist #print('nov_cur',nov_cur) V = nov_cur vaelist = [ [] for i in range(V)] L_list = [ None for _ in range(V)] dfs_restart = [0 for _ in range(V)] prev_ee = [None for i in range(E*2)] for e in elist: eid,u = e['id'],e['u'] vaelist[u].append(eid) def output_v(): for i,va in enumerate(vaelist): print(i,va) print() def output_e(): for i,lv in enumerate(L_list): print(f'i:{i} L:{lv}') for i,e in enumerate(elist): print(i,e) if i==E-1: print() print() #print(f's,t:{s,t} N,M:{N,M} V,E:{V,E}') #output_v() #output_e() #print(vaelist) def bfs(): global L_list L_list = [ -1 for _ in range(V)] L_list[s] = 0 q = deque() q.append(s) while q: u = q.popleft() #print(vaelist[u]) for loc_e in vaelist[u]: e = elist[loc_e] v,c,f = e['v'], e['c'], e['f'] #print(e) if f < c and L_list[v] == -1: L_list[v] = L_list[u]+1 q.append(v) def dfs_rec(u,res_min): if u== t: return res_min for loc_e in vaelist[u]: e, e_rev = elist[loc_e], elist [(loc_e+E) % (E+E)] v, c, f = e['v'], e['c'], e['f'] if c-f > 0 and L_list[u] < L_list[v]: d = dfs_rec(v,min( c-f, res_min)) if d > 0: e['f'] += d e_rev['f'] -=d v, c, f = e['v'], e['c'], e['f'] return d return 0 def dfs(): stack =[(None,s,INF)] last_e,res_min_last = None, None break1 = False while stack: came_e, u, res_min = stack.pop(-1) for i in range(dfs_restart[u], len(vaelist[u])): loc_e = vaelist[u][i] e = elist[loc_e] dfs_restart[u] = i v, c, f = e['v'], e['c'], e['f'] if f < c and L_list[u] < L_list[v]: prev_ee[loc_e] = came_e res_min_next = min( c-f ,res_min) #print('rmn:',res_min,f,res_min_next) if v == t: last_e, res_min_last = loc_e, res_min_next #print('reached', last_e, res_min_next) break1 = True break stack.append((loc_e,v, res_min_next) ) if break1: pass break if last_e == None: return 0 else: cur_e = last_e while cur_e != None: e, e_rev = elist[cur_e], elist[ (cur_e + E) % (E+E) ] e['f'] += res_min_last e_rev['f'] -= res_min_last cur_e = prev_ee[cur_e] return res_min_last f_sum = 0 while True: bfs() if L_list[t] == -1: break dfs_restart = [0 for _ in range(V)] while True: new_f = dfs() #new_f = dfs_rec(s,INF) #output_e() f_sum += new_f if new_f == 0: break #print('dfs-phase-end') print(f_sum) #output_e()