AtCoder Regular Contest 079

Submission #1463078

Source codeソースコード

import sys
import heapq
readline = sys.stdin.readline

N, M = map(int, readline().split())
edges = [[] for _ in [None]*N]
for _ in [None]*M:
    a, b = map(int, readline().split())
    a, b = a-1, b-1
    edges[a].append((b, 1))
    edges[b].append((a, 1))


def dijkstra(n, edges, start):
    heappop, heappush = heapq.heappop, heapq.heappush
    inf = float("inf")
    vertices = [inf] * n
    vertices[start] = 0
    q, rem = [(0, start)], n - 1

    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1

        for dest, _cost in edges[v]:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))

    return vertices

print("POSSIBLE" if dijkstra(N, edges, 0)[N-1] == 2 else "IMPOSSIBLE")

Submission

Task問題 C - Cat Snuke and a Voyage
User nameユーザ名 htkb
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 300
Source lengthソースコード長 895 Byte
File nameファイル名
Exec time実行時間 1308 ms
Memory usageメモリ使用量 72060 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0,example1,example2,example3
All 300 / 300 example0,example1,example2,example3,last0,last1,many0,many1,rand0,rand1,rand2

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
example0 AC 19 ms 3064 KB
example1 AC 18 ms 3064 KB
example2 AC 44 ms 11080 KB
example3 AC 18 ms 3064 KB
last0 AC 1308 ms 67576 KB
last1 AC 1291 ms 67576 KB
many0 AC 980 ms 71912 KB
many1 AC 1282 ms 72060 KB
rand0 AC 749 ms 50384 KB
rand1 AC 1236 ms 65640 KB
rand2 AC 468 ms 45916 KB