[백준]16064 coolest ski route #플로이드와샬 정석

1. 풀이

영어 문제이지만 알고리즘분류와 input만 봐도 뭘구해야 하는지 알 수 있다.

점수가 최대가 되는 route를 찾는 문제이므로 point간 점수에 -1을 곱해준 뒤 최단거리를 찾으면 된다.

이때 시작점과 종료지점이 모든점이 될 수 있기 때문에 플로이드로 모든 정점들 사이의 거리를 구해주고 그중 가장 작은 값을 구해준다 (그다음 -1을 곱해준다)

추가로 이 문제를 통해 플로이드 문제를 풀 때 해야하는 작업들을 정리한다

 

2. 플로이드 와샬 구현

딱 세가지만 기억!!!!!!

 

(1) 초기값을 +무한대로 초기화 한다.

- 최단거리를 찾는 문제이다. 시작점을 제외한 모든점들은 당연히 +무한대로 초기화한다.

dist=[[INF for j in range(n)] for i in range(n)]

 

(2) 자기자신으로 가는 값은 0으로 초기화한다.

for i in range(n):
    dist[i][i]=0

 

(3) for문돌기

- 첫번째 포문은 중간거점 k, 두번째 포문은 시작점i, 세번째 포문은 끝점 j

for k in range(n):
    for i in range(n):
        for j in range(n):
            newDist=dist[i][k]+dist[k][j]
            if newDist<dist[i][j]:
                dist[i][j]=newDist

 

- 아직 길이 나지 않은(시작점으로부터 방문되지않은) 부분은 탐색을 중지한다 (시간을 많이 줄일 수 있다)

for k in range(n):
    for i in range(n):
        if dist[i][k]==INF:
            continue
        for j in range(n):
            if dist[k][j]==INF:
                continue
            newDist=dist[i][k]+dist[k][j]
            if newDist<dist[i][j]:
                dist[i][j]=newDist

 

 

3. 소스코드

import sys
n,m=map(int,input().split())
INF=9876543210

dist=[[INF for j in range(n)] for i in range(n)]
for i in range(n):
    dist[i][i]=0

for _ in range(m):
    a,b,c=map(int,sys.stdin.readline().rstrip().split())
    a-=1
    b-=1
    c*=-1
    if dist[a][b]!=INF:
        if c<dist[a][b]:
            dist[a][b]=c
    else:
        dist[a][b]=c

for k in range(n):
    for i in range(n):
        if dist[i][k]==INF:
            continue
        for j in range(n):
            if dist[k][j]==INF:
                continue
            newDist=dist[i][k]+dist[k][j]
            if newDist<dist[i][j]:
                dist[i][j]=newDist

print(-min([min(dist[i]) for i in range(n)]))

 

 

 

* 아래처럼 밸만포드로 풀어봤는데 시간초과다..  어디서 더 줄여아할지 모르겠다. 혹시 아시겠으면 알려주세요..

INF=0

n,m=map(int,input().split())

edge=[]
for i in range(m):
    a,b,c=map(int,input().split())
    edge.append([a,b,-c])

def bellman(start):
    dist=[1 for i in range(n+1)]
    dist[start]=0
    for i in range(n-1):
        isUpdate=False
        for a,b,c in edge:
            if dist[a]==1:
                continue
            newDist=dist[a]+c
            if newDist<dist[b]:
                dist[b]=newDist
                isUpdate=True
    return -min(dist)

ans=0
for i in range(1,n+1):
    temp=bellman(i)
    if ans<temp:
        ans=temp

print(ans)