Submission #24509725

Source Code Expand

#隣接リスト作成
N,M=map(int,input().split())
MOD=10**9+7
G=[[]for _ in range(N)] #隣接リスト
for _ in range(M):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)


#DFS/BFS 非再帰
from collections import deque

i_init,v_init,v_yet=0,0,10**8

D=deque()
D.appendleft([i_init,v_init])

A=[0]*N
A[0]=1
V=[v_yet]*N
V[i_init]=v_init



#探索
while D:
  i,v=D.popleft()
  v_new=v+1
  for j in G[i]:
    if v_new>V[j]:
      continue
    A[j]+=A[i]
    if v_new<V[j]:
      A[j]=A[i]
      D.append([j,v_new]) #BFS
    A[j]%=MOD
    V[j]=v_new
    

print(A[-1]%MOD)

Submission Info

Submission Time
Task D - Number of Shortest paths
User Pandruant
Language PyPy3 (7.3.0)
Score 400
Code Size 598 Byte
Status AC
Exec Time 521 ms
Memory 104884 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Case Name Status Exec Time Memory
random_01.txt AC 519 ms 99396 KiB
random_02.txt AC 428 ms 92748 KiB
random_03.txt AC 304 ms 90452 KiB
random_04.txt AC 254 ms 78604 KiB
random_05.txt AC 467 ms 98320 KiB
random_06.txt AC 405 ms 90216 KiB
random_07.txt AC 182 ms 84960 KiB
random_08.txt AC 138 ms 76196 KiB
random_09.txt AC 503 ms 98480 KiB
random_10.txt AC 460 ms 91976 KiB
random_11.txt AC 203 ms 85204 KiB
random_12.txt AC 115 ms 75900 KiB
random_13.txt AC 519 ms 99580 KiB
random_14.txt AC 503 ms 98232 KiB
random_15.txt AC 447 ms 95808 KiB
random_16.txt AC 263 ms 84312 KiB
random_17.txt AC 521 ms 99612 KiB
random_18.txt AC 450 ms 87832 KiB
random_19.txt AC 464 ms 96348 KiB
random_20.txt AC 231 ms 79964 KiB
random_31.txt AC 300 ms 94188 KiB
random_32.txt AC 409 ms 104884 KiB
random_33.txt AC 499 ms 94840 KiB
random_34.txt AC 428 ms 83864 KiB
random_35.txt AC 429 ms 83940 KiB
random_36.txt AC 482 ms 89748 KiB
sample_01.txt AC 58 ms 64876 KiB
sample_02.txt AC 54 ms 64764 KiB
sample_03.txt AC 56 ms 64852 KiB
sample_04.txt AC 59 ms 64964 KiB