1. 문제 설명

여행 가자

2. 문제 분석

플로이드-워셜 알고리즘으로 각 노드 별 다른 모든 노드에 대한 최단 경로를 탐색하고, 여행 계획으로 들어오는 인접 노드 간 최단 경로가 무한(즉 경로 없는 노드들)인지 체크한다.

3. 나의 풀이

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
nodes = []
INF = sys.maxsize
for i in range(n):
    nodes.append(list(map(int, sys.stdin.readline().rstrip().split())))
    for j in range(n):
        if i != j and nodes[i][j] == 0:
            nodes[i][j] = INF

for k in range(n):
    for i in range(n):
        for j in range(n):
            if nodes[i][j] > nodes[i][k] + nodes[k][j]:
                nodes[i][j] = nodes[i][k] + nodes[k][j]

plan = list(map(int, sys.stdin.readline().rstrip().split()))

reachable = True
for i in range(len(plan)-1):
    if nodes[plan[i]-1][plan[i+1]-1] == INF:
        reachable = False
        break

if reachable: print('YES')
else: print('NO')