[Python]최단경로 백준 1956

 문제

 https://www.acmicpc.net/problem/1956

사이클이 될수있는 구간중 가장 짧은 경로 구하는것이다.

시작지점이 정해지지 않았고 모든구간에서 확인해야 하기때문에 플로이드 와샬을 

이용해  모든 정점에서 모든 정점으로 가는  최소 거리를 구한뒤 i->i가 가장짧은것을 

구하면된다. 

역시 알고리즘의 복잡도가 O(V^3)이라서 파이썬으로는 통과할수 없었다.

pypy3를 이용하여 제출하면 성공할수있다.

 

import sys
 
V,E=map(int,sys.stdin.readline().split())
INF=sys.maxsize
matrix=[[INF for _ in range(V+1)] for _ in range(V+1)]
for _ in range(E):
    a,b,c=map(int,sys.stdin.readline().split())
    matrix[a][b]=c#a->b가는 거리 c
 
 
for k in range(1,V+1):#플로이드 와샬 k노드를 거쳐갈때
    for i in range(1,V+1):
        for j in range(1,V+1):
            matrix[i][j]=min(matrix[i][j],matrix[i][k]+matrix[k][j])
 
result=INF
for i in range(1,V+1):#돌아오는 사이클 중 가장 최소거리 찾기
        result=min(result,matrix[i][i])
 
if result==INF:
    print(-1)
else:
    print(result)