[백준 파이썬 1956] 운동 풀이

[백준 파이썬 1956] 운동 풀이

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

1956번: 운동

문제

v개의 마을와 E개의 도로로 구성되어 있는 도시가 있다 (각 도로는 일반 통행)

각 도시를 1부터 V 까지 번호를 매겨져 있다

당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.

 

입력

첫줄에는 V,E 가 주이면 다음주부터는 a,b,c 가 주어진다

a번 마을에서 b번 마을로 가는 거리가 c인 도로라는 의미인다 

출력

최소 사이클의 도로 길이의 합을 출력한다 

불가능 하면 -1을 출력한다 

풀이

플로이드 워셜을 이용하여 풀었다

플로이드 워셜 알고리즘은 모든 점에 모든점까지의 최단 경로를 구할수 있는 알고리즘으로 

주어진 도로의 비용을 제외하고는 모두다 거리를 무한으로 지정하고 

 최단경로를 구하면 자기자신으로 다시 돌아오는 최단 경로를 구할수 있다

코드

inf=int(1e9)
n,m=map(int,input().split())

graph=[[inf]*(n+1) for _ in range(n+1)]
ans=inf
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a][b]=c #주어진 정보 저장

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            graph[i][j]=min(graph[i][k]+graph[k][j],graph[i][j])
            #최단 경로 구하기


print(graph)
for i in range(1,n+1):
    if ans>graph[i][i]: #가장 짧은 사이크 구하기
        ans=graph[i][i]
if ans==inf:
    print(-1)
else:
    print(ans)

 

결과

 

python3로 돌리면 시간 초과가 나오는데 시간 초과가 나오는이유는 3중 for문을 돌리기 때문에 pypy로 돌려야지 시간초과가 나오지 않는다

python3로 풀려먼 다른 최단경로 구하는 알고리즘인 다익스트라 알고리즘을 사용하면 풀수 있다는 것을 다른 글들을 보고다익스트라로 풀어봤지만 풀지 못하였다 

 

 

----추가..

다이스트라로 다른사람들 코드 참고해가면서 풀었는데 메모리 초과가 나온다 조건이 옛날하고 달라졌는지 모르겠지만 

맞췄다고 하는 사람들껄로도 메모리 초과가 뜨는걸 확인횄다