幅優先探索
C - Cat Snuke and a Voyage
O(N)
from asyncio import QueueFull import sys import math import heapq import itertools from collections import deque from functools import reduce # main def main(): N, M = list(map(int, input().split())) G = [] for _ in range(N): G.append([]) for i in range(M): a, b = list(map(int, input().split())) a -= 1 b -= 1 G[a].append(b) G[b].append(a) dist = [] for _ in range(N): dist.append(-1) Q = deque() Q.append(0) dist[0] = 0 while len(Q) > 0: i = Q.popleft() for j in G[i]: if dist[j] == -1: dist[j] = dist[i] + 1 Q.append(j) if dist[N-1] == 2: print("POSSIBLE") else: print("IMPOSSIBLE") # エントリポイント if __name__ == '__main__': main()
heapqを使用し、ダイクストラに対応。
from asyncio import QueueFull import sys import math import heapq import itertools from collections import deque from functools import reduce # main def main(): N, M = list(map(int, input().split())) G = [] for _ in range(N): G.append([]) for i in range(M): a, b = list(map(int, input().split())) a -= 1 b -= 1 G[a].append(b) G[b].append(a) dist = [] done = [] for _ in range(N): dist.append(-1) done.append(False) Q = [] heapq.heappush(Q, (0, 0)) dist[0] = 0 while len(Q) > 0: d, i = heapq.heappop(Q) if done[i]: continue done[i] = True for j in G[i]: x = 1 if dist[j] == -1 or dist[j] > dist[i] + x: dist[j] = dist[i] + x heapq.heappush(Q, (dist[j], j)) if dist[N-1] == 2: print("POSSIBLE") else: print("IMPOSSIBLE") # エントリポイント if __name__ == '__main__': main()
D - 単一始点最短経路問題
O(N)
import sys import math import heapq import itertools from collections import deque from functools import reduce # main def main(): N, M = list(map(int, input().split())) G = [] dist = [] done = [] for _ in range(N): G.append([]) dist.append(-1) done.append(False) for _ in range(M): u, v, c = list(map(int, input().split())) G[u].append((v, c)) Q = [] heapq.heappush(Q, (0, 0)) dist[0] = 0 while len(Q) > 0: d, i = heapq.heappop(Q) if done[i]: continue done[i] = True for j, c in G[i]: if dist[j] == -1 or dist[j] > dist[i] + c: dist[j] = dist[i] + c heapq.heappush(Q, (dist[j], j)) print(dist[N-1]) # エントリポイント if __name__ == '__main__': main()