Courses

그래프 이론

플로이드 알고리즘

Module: 플로이드 알고리즘

Problem

9 /10

플로이드 - 존재

Theory Click to read/hide

마이너스 가중치의 순환 경로는 불가능해집니다.

Problem

방향 가중치 그래프가 제공됩니다. 인접 행렬을 사용하여 정점 사이에 최단 경로가 있는지 여부를 각 정점 쌍에 대해 결정해야 합니다.

설명: 다음 두 가지 이유로 최단 경로가 존재하지 않을 수 있습니다.

경로가 없습니다
무게가 임의로 작은 경로가 있습니다.

입력

입력 파일의 첫 번째 줄에는 N (1 <=N <=100) — 그래프 정점의 수. 다음 N 행에는 각각 N개의 숫자가 포함됩니다. 그래프의 인접 행렬(i번째 줄의 j번째 숫자는 꼭지점 i에서 꼭지점 j까지의 가장자리 가중치에 해당): 숫자 0은 가장자리가 없음을 의미하고 다른 모든 숫자 — 해당 무게의 가장자리가 있습니다. 모든 모듈로 숫자는 100을 초과하지 않습니다.

출력

N개의 숫자를 N줄로 인쇄합니다. i번째 줄의 j번째 숫자는 정점 i에서 정점 j까지의 최단 경로에 해당해야 합니다. 경로가 없으면 0, 최단 경로가 있으면 1, 경로는 있지만 임의의 작은 가중치가 있는 경로가 있으면 2가 되어야 합니다.

예 <헤드> <일># <몸>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking