백준 1238(파티) - python

접근

최단거리를 찾는 문제중에서 특정 정점에서 특정 정점까지 가는 문제라 bfs, 다익스트라 알고리즘으로

풀 생각을 했다. 가중치가 없어 bfs로도 풀수있겠다는 생각을 했지만 경로 알고리즘을 학습하고 싶어

시간 제한을 생각하지않고 다익스트라, 플로이드 워셜으로 풀어봤다.

 

플로이드 워셜(시간초과)

import sys
input = sys.stdin.readline

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

M = [[101 for _ in range(n)] for _ in range(n)]

for i in range(m):
    s, f, v = map(int,input().split())
    M[s-1][f-1] = v

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


for k in range(n):
    for i in range(n):
        for j in range(n):
            M[i][j] = min(M[i][j],M[i][k] + M[k][j])

maxv = 0
for i in range(n):
    if maxv < M[i][t-1]+ M[t-1][i]:
        maxv = M[i][t-1]+ M[t-1][i]
print(maxv)

 

정석적인 다익스트라(시간초과)

import sys
input = sys.stdin.readline

n, m , t = map(int,input().split())
mn = 10000*10000
G = [[] for _ in range(n+1)]
r =  [0]*(n+1)
for i in range(m):
    s, f, v = map(int,input().split())
    G[s].append((f,v))

def minvi():
    minv= mn
    mini= -1
    for i in range(1,n+1):
        if visit[i]:
            continue
        if d[i] < minv:
            minv = d[i]
            mini = i
    return mini


def dik(start):
    d[start] = 0
    visit[start] = True
    for f in G[start]:
        d[f[0]] = f[1]
    for _ in range(n):
        ti = minvi()
        if ti == -1:
            break
        visit[ti] = True
        for f in G[ti]:
            d[f[0]] = min(d[f[0]], d[ti]+f[1])


for i in range(1,n+1):
    visit = [False]*(n+1)
    d = [mn] * (n+1)
    if i != t:
        dik(i)
        if d[t] == mn:
            continue
        r[i] += d[t]
    else:
        dik(i)
        for j in range(1,n+1):
            if d[j] == mn:
                continue
            if j !=t:
                r[j] += d[j]

result = 0
for i in r[1:]:
    if 0 < i < mn and i > result:
        result = i

print(result)

 

heapq 다익스트라

import sys
input = sys.stdin.readline
import heapq

n, m , t = map(int,input().split())
mn = 10**9
G = [[] for _ in range(n+1)]
r =  [0]*(n+1)


for i in range(m):
    s, f, v = map(int,input().split())
    G[s].append((f,v))

def dik(start):
    h = []
    heapq.heappush(h,(0,start))
    d[start] = 0
    while h:
        v, ti = heapq.heappop(h)
        for ti2, v2 in G[ti]:
            if d[ti2] > v+v2:
                d[ti2] = v+v2
                heapq.heappush(h,(v+v2,ti2))

for i in range(1,n+1):
    d = [mn] * (n+1)
    if i != t:
        dik(i)
        if d[t] >= mn:
            continue
        r[i] += d[t]
    else:
        dik(i)
        for j in range(1,n+1):
            if d[j] >= mn:
                continue
            if j !=t:
                r[j] += d[j]

result = 0
for i in r[1:]:
    if 0 < i < mn and i > result:
        result = i

print(result)

 

최적화한 코드

t에서 다른곳까지의 거리를 구하고 , t로 도착하는 노드를 시작노드로 만들어서 다시 거리를 구해 이를 합해준다.

이를 위해 초기 distance 를 -1 로 초기화하는데 heapq는 항상 최저 값으로 유지되기때문에 가장 먼저 업데이트 되는게 해당

목적지까지 가는 최적의 값이다.

import sys
input = sys.stdin.readline
from heapq import heappop, heappush

n, m , t = map(int,input().split())
G = [[] for _ in range(n+1)]
Gr = [[] for _ in range(n+1)]


for i in range(m):
    s, f, v = map(int,input().split())
    G[s].append((f,v))
    Gr[f].append((s,v))

def dik(start, G):
    h = []
    d = [-1] * (n+1)
    heappush(h,(0,start))
    while h:
        v, ti = heappop(h)
        if d[ti] != -1:
            continue
        d[ti] = v
        for ti2, v2 in G[ti]:
            if d[ti2] == -1:
                heappush(h,(v+v2,ti2))
    return d


dist = dik(t, G)
reversed_dist = dik(t, Gr)

sum_list = [x+y for x,y, in zip(dist,reversed_dist)]
print(max(sum_list[1:]))