結果
| 問題 |
No.1600 Many Shortest Path Problems
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-09 20:57:31 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,260 bytes |
| コンパイル時間 | 254 ms |
| コンパイル使用メモリ | 82,396 KB |
| 実行使用メモリ | 56,488 KB |
| 最終ジャッジ日時 | 2025-04-09 20:59:31 |
| 合計ジャッジ時間 | 9,276 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | AC * 4 TLE * 1 -- * 46 |
ソースコード
import sys
from collections import defaultdict, deque
sys.setrecursionlimit(1 << 25)
MOD = 10**9 + 7
def main():
input = sys.stdin.read().split()
ptr = 0
N, M = int(input[ptr]), int(input[ptr+1])
ptr += 2
edges = []
for i in range(M):
a = int(input[ptr])-1
b = int(input[ptr+1])-1
ptr += 2
edges.append((a, b, i+1))
parent = list(range(N))
rank = [1] * N
mst_edges = []
non_mst_edges = []
adj = [[] for _ in range(N)]
edge_set = set()
def find(u):
while parent[u] != u:
parent[u] = parent[parent[u]]
u = parent[u]
return u
def union(u, v):
u_root = find(u)
v_root = find(v)
if u_root == v_root:
return False
if rank[u_root] < rank[v_root]:
parent[u_root] = v_root
rank[v_root] += rank[u_root]
else:
parent[v_root] = u_root
rank[u_root] += v_root
return True
for idx, (a, b, i) in enumerate(edges):
if union(a, b):
mst_edges.append((a, b, i))
edge_set.add((a, b, i))
adj[a].append((b, i))
adj[b].append((a, i))
else:
non_mst_edges.append((a, b, i))
LOG = 20
up = [[-1] * N for _ in range(LOG)]
depth = [0] * N
sum_from_root = [0] * N
parent_edge = [[] for _ in range(N)]
q = deque()
root = 0
q.append((root, -1))
while q:
u, p = q.popleft()
for v, i in adj[u]:
if v == p:
continue
up[0][v] = u
depth[v] = depth[u] + 1
sum_from_root[v] = (sum_from_root[u] + pow(2, i, MOD)) % MOD
parent_edge[v] = (u, i)
q.append((v, u))
up[0][root] = -1
for k in range(1, LOG):
for v in range(N):
if up[k-1][v] == -1:
up[k][v] = -1
else:
up[k][v] = up[k-1][up[k-1][v]]
def lca(u, v):
if depth[u] < depth[v]:
u, v = v, u
for k in range(LOG-1, -1, -1):
if depth[u] - (1 << k) >= depth[v]:
u = up[k][u]
if u == v:
return u
for k in range(LOG-1, -1, -1):
if up[k][u] != up[k][v]:
u = up[k][u]
v = up[k][v]
return up[0][u]
def get_path_sum(u, v):
ancestor = lca(u, v)
return (sum_from_root[u] + sum_from_root[v] - 2 * sum_from_root[ancestor]) % MOD
best_bridge = defaultdict(lambda: (float('inf'), None, None))
for a, b, i in non_mst_edges:
path = []
u = a
v = b
l = lca(u, v)
path_edges = set()
current_u = u
while current_u != l:
parent_u = up[0][current_u]
for p_edge in adj[current_u]:
if p_edge[0] == parent_u:
e = (current_u, parent_u, p_edge[1])
break
path_edges.add(e)
current_u = parent_u
current_v = v
while current_v != l:
parent_v = up[0][current_v]
for p_edge in adj[current_v]:
if p_edge[0] == parent_v:
e = (current_v, parent_v, p_edge[1])
break
path_edges.add(e)
current_v = parent_v
for edge in path_edges:
a_edge, b_edge, idx = edge
if best_bridge[idx][0] > i:
best_bridge[idx] = (i, a, b)
Q = int(input[ptr])
ptr += 1
for _ in range(Q):
x = int(input[ptr])-1
y = int(input[ptr+1])-1
z = int(input[ptr+2])
ptr += 3
if x == y:
print(0)
continue
def find_k(x, y):
u = x
v = y
l = lca(u, v)
max_edge = 0
current_u = u
while current_u != l:
parent_u = up[0][current_u]
for p_edge in adj[current_u]:
if p_edge[0] == parent_u:
max_edge = max(max_edge, p_edge[1])
break
current_u = parent_u
current_v = v
while current_v != l:
parent_v = up[0][current_v]
for p_edge in adj[current_v]:
if p_edge[0] == parent_v:
max_edge = max(max_edge, p_edge[1])
break
current_v = parent_v
return max_edge
K = find_k(x, y)
original_sum = get_path_sum(x, y) % MOD
if z > K:
print(original_sum)
continue
def is_edge_in_path(x, y, z_val):
edge_found = False
l = lca(x, y)
current = x
while current != l:
parent_current = up[0][current]
for p_edge in adj[current]:
if p_edge[0] == parent_current:
if p_edge[1] == z_val:
edge_found = True
break
current = parent_current
if edge_found:
break
if not edge_found:
current = y
while current != l:
parent_current = up[0][current]
for p_edge in adj[current]:
if p_edge[0] == parent_current:
if p_edge[1] == z_val:
edge_found = True
break
current = parent_current
if edge_found:
break
return edge_found
if not is_edge_in_path(x, y, z):
print(original_sum)
continue
if z not in best_bridge:
print(-1)
continue
bridge_info = best_bridge.get(z, (float('inf'), None, None))
if bridge_info[0] == float('inf'):
print(-1)
continue
L, a, b = bridge_info
new_sum = (pow(2, L, MOD) + get_path_sum(x, a) + get_path_sum(b, y)) % MOD
print(new_sum if new_sum != 0 else -1)
return
if __name__ == '__main__':
main()