Submission #5717325

Source Code Expand

# 接続行列のべき
MOD = 10**9 + 7
N = int(input())
a,b = map(int,input().split())
M = int(input())

import numpy as np
graph = np.zeros((N+1,N+1),dtype=np.int64)

for _ in range(M):
  x,y = map(int,input().split())
  graph[x,y] += 1
  graph[y,x] += 1

v = np.zeros(N+1,dtype=np.int64)
v[a] = 1

while v[b] == 0:
  v = np.dot(graph,v)
  # 0でないものを0にしないように除算
  select = (v > 0)
  v[select] %= MOD
  v[select & (v==0)] += MOD

print(v[b]%MOD)

Submission Info

Submission Time
Task C - 正直者の高橋くん
User maspy
Language Python (3.4.3)
Score 100
Code Size 498 Byte
Status AC
Exec Time 157 ms
Memory 12520 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 32
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 149 ms 12408 KiB
subtask0_sample_02.txt AC 149 ms 12404 KiB
subtask1_01.txt AC 153 ms 12520 KiB
subtask1_02.txt AC 152 ms 12520 KiB
subtask1_03.txt AC 149 ms 12408 KiB
subtask1_04.txt AC 152 ms 12516 KiB
subtask1_05.txt AC 151 ms 12520 KiB
subtask1_06.txt AC 150 ms 12404 KiB
subtask1_07.txt AC 149 ms 12396 KiB
subtask1_08.txt AC 150 ms 12412 KiB
subtask1_09.txt AC 157 ms 12276 KiB
subtask1_10.txt AC 149 ms 12396 KiB
subtask1_11.txt AC 150 ms 12520 KiB
subtask1_12.txt AC 150 ms 12516 KiB
subtask1_13.txt AC 150 ms 12516 KiB
subtask1_14.txt AC 152 ms 12520 KiB
subtask1_15.txt AC 153 ms 12520 KiB
subtask1_16.txt AC 151 ms 12520 KiB
subtask1_17.txt AC 151 ms 12520 KiB
subtask1_18.txt AC 150 ms 12520 KiB
subtask1_19.txt AC 152 ms 12520 KiB
subtask1_20.txt AC 150 ms 12520 KiB
subtask1_21.txt AC 150 ms 12520 KiB
subtask1_22.txt AC 150 ms 12520 KiB
subtask1_23.txt AC 150 ms 12516 KiB
subtask1_24.txt AC 150 ms 12520 KiB
subtask1_25.txt AC 149 ms 12516 KiB
subtask1_26.txt AC 150 ms 12520 KiB
subtask1_27.txt AC 150 ms 12520 KiB
subtask1_28.txt AC 151 ms 12520 KiB
subtask1_29.txt AC 149 ms 12404 KiB
subtask1_30.txt AC 149 ms 12408 KiB