-
Notifications
You must be signed in to change notification settings - Fork 6
/
roadtimes.py
64 lines (61 loc) · 3.15 KB
/
roadtimes.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import sys; input = sys.stdin.readline; from heapq import *; from array import *
C = []; V = int(input()); INF = 10**9; EPS = 1e-5; g = [{} for _ in range(V)]; R = {}; A = []; E = array('h')
for i in range(V):
a = [*map(int, input().split())]
for j in range(V):
if a[j] > 0: g[i][j] = a[j]; R[(i, j)] = len(R); E.append(a[j])
for _ in range(int(input())):
s, t, d = map(int, input().split()); D = array('i', [INF]*V); D[s] = 0; pq = [s]; a = array('i', [0]*len(R)); P = array('b', [-1]*V); p = t
while pq:
dd, vv = divmod(heappop(pq), V)
if dd != D[vv]: continue
for nn in g[vv]:
if D[nn] > (new:=dd+g[vv][nn]): P[nn] = vv; D[nn] = new; heappush(pq, new*V+nn)
while P[p] != -1: a[R[(P[p], p)]] = 1; d -= g[P[p]][p]; p = P[p]
a.append(d); A.append(a); A.append(array('i', [-i for i in a]))
for i in range(len(R)): e = E[i]; a = [0]*len(R)+[e]; a[i] = 1; A.append(array('i', a))
for _ in range(int(input())):
s, t = map(int, input().split()); D = array('i', [INF]*V); D[s] = 0; pq = [s]; c = array('b', [0]*len(R)); P = array('b', [-1]*V); p = t; z = 0
while pq:
dd, vv = divmod(heappop(pq), V)
if dd != D[vv]: continue
for nn in g[vv]:
if D[nn] > (new:=dd+g[vv][nn]): P[nn] = vv; D[nn] = new; heappush(pq, new*V+nn)
while P[p] != -1: c[R[(P[p], p)]] = 1; z += g[P[p]][p]; p = P[p]
C.append((s, t, z, c))
m = len(A); n = len(A[0])-1; X = n+2; D0 = [0]*X*(m+2+2*len(C)); N = [*range(n)]+[-1]; B = [0]*m; D0[-X+n] = 1; r = 0
for i in range(m):
for j in range(n): D0[i*X+j] = A[i][j]
B[i] = n+i; D0[i*X+n] = -1; D0[i*X+X-1] = A[i][-1]
for i in range(1, m):
if D0[i*X+X-1] < D0[r*X+X-1]: r = i
for i in range(len(C)):
*_, c = C[i]
for j in range(len(c)): D0[(m+2*i)*X+j] = c[j]; D0[(m+2*i+1)*X+j] = -c[j]
def pivot(D, N, B, r, s):
k = 1/D[r*X+s]
for i in range(len(D)//X):
if i == r: continue
for j in range(X):
if j != s: D[i*X+j] -= D[r*X+j]*D[i*X+s]*k
for i in range(X): D[r*X+i] *= k
for i in range(len(D)//X): D[i*X+s] *= -k
D[r*X+s] = k; B[r], N[s] = N[s], B[r]
def find(D, N, B, p):
x = -p-1
while True:
s = r = -1
for i in range(n+1):
if (p==0 or N[i] != -1) and (s == -1 or D[x*X+i] < D[x*X+s] or (D[x*X+i]==D[x*X+s] and N[i] < N[s])): s = i
if D[x*X+s] > -EPS: break
for i in range(m):
if D[i*X+s] > EPS and (r == -1 or D[i*X+X-1]/D[i*X+s] < D[r*X+X-1]/D[r*X+s] or (D[i*X+X-1]*D[r*X+s] == D[r*X+X-1]*D[i*X+s] and B[i] < B[r])): r = i
pivot(D, N, B, r, s)
if D0[r*X+X-1] < -EPS: pivot(D0, N, B, r, n); find(D0, N, B, 0)
for i in range(m):
if B[i] != -1: continue
s = -1
for j in range(n):
if s == -1 or D0[i*X+j] < D0[i*X+s] or (D0[i*X+j] == D0[i*X+s] and N[j] < N[s]): s = j
pivot(D0, N, B, i, s)
for i in range(len(C)): s, t, z, _ = C[i]; D = D0[:m*X]+D0[(m+2*i)*X:(m+2*i+1)*X]+D0[-X:]; find(D, array('h', N), array('h', B), 1); L = z-D[m*X+X-1]; D = D0[:m*X]+D0[(m+2*i+1)*X:(m+2*i+2)*X]+D0[-X:]; find(D, array('h', N), array('h', B), 1); H = z+D[m*X+X-1]; print(s, t, L, H)