운동

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

1956번: 운동

문제요약:

도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.

 

난이도 :

골드4

 

소요시간:

20분

 

제출횟수:

1회

 

코딩:

import sys
input = sys.stdin.readline
v,e = map(int,input().split())
INF = int(1e9)
arr = [[INF]*(v+1) for _ in range(v+1)]

for _ in range(e):
    s,e,c = map(int,input().split())
    arr[s][e] = c

for k in range(1,v+1):
    for y in range(1,v+1):
        for x in range(1,v+1):
            if arr[y][x] > arr[y][k] +arr[k][x]:
                arr[y][x] = arr[y][k] +arr[k][x]
temp = []
for y in range(1,v+1):
    for x in range(y+1,v+1):
            temp.append(arr[y][x] + arr[x][y])
        
ans = min(temp)
print(ans if ans<INF else -1)

처음 제출한 코드입니다. pypy3로 통과를 받았으며, 플로이드 워셜을 통해 해결했습니다. 다만 이때 마지막에서 사이클을 찾는경우에서 두개를 굳이 합하지 않고, 

    for i in range(1,v+1):
        mini = min(mini, graph[i][i])

다음과 같이 처리를 해줘도 같은 의미임을 알 수 있다.

그리고 이를 python으로 제출하면 시간초과를 받게 되지만

import sys
input = sys.stdin.readline
v,e = map(int,input().split())
INF = int(1e9)
arr = [[INF]*(v+1) for _ in range(v+1)]
for _ in range(e):
        s,e,c = map(int,input().split())
        arr[s][e] = c
    
def solve():
    for k in range(1,v+1):
        for y in range(1,v+1):
            for x in range(1,v+1):
                if arr[y][x] > arr[y][k] +arr[k][x]:
                    arr[y][x] = arr[y][k] +arr[k][x]
    temp = []
    for y in range(1,v+1):
        for x in range(y+1,v+1):
                temp.append(arr[y][x] + arr[x][y])
            
    ans = min(temp)
    print(ans if ans<INF else -1)
solve()

다음과 같이 함수로 감싸게 된다면 시간초과를 피할 수 있다. 이유는 찾아봐야 할 것 같다. 함수로 묵자.