[python]백준 1238번 - 파티

1238번: 파티 (acmicpc.net)

1238번: 파티

정답 코드입니당

import sys
import heapq
input = sys.stdin.readline
n, m, x = map(int,input().split())

INF = int(1e9) #10억
arr = [[INF for j in range(n+1)] for i in range(n+1)]
graph = [[] for i in range(n+1)]
for i in range(1,m+1):
    start, end, cost = map(int, input().split())
    graph[start].append((end, cost))
x

def dijkstra(start, end):
    q = []
    heapq.heappush(q, (0, start))
    distance = [INF] * (n+1)
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance[end]

sum = 0
for i in range(1, n+1):
    a = dijkstra(i, x)
    b = dijkstra(x, i)
    sum = max(sum, a + b)

print(sum)

---

 
지금 약간 오랜만에 파이썬 해서 이차원 배열 쓰는 법부터 해서 계속 찾아보는 중인데

약간 속터질거 가타요

오찟

그 입력범위가 1000이라서 플로이드 워셜로 하면 n*3?이런 식으로 되니까 시간초과 나서 안된대요...왠지 안 되더라구요...
플로이드 워셜로 한 코드입니당

import sys
input = sys.stdin.readline
n, m, x = map(int,input().split())

INF = 999999;
arr = [[INF for j in range(n+1)] for i in range(n+1)]

for i in range(1,m+1):
    start, end, cost = map(int, input().split())
    arr[start][end] = cost
    if(i <= n):
        arr[i][i] = 0

for i in range(1,n+1):
    for j in range(1,n+1):
        if arr[j][i] == INF:
            continue
        for k in range(1,n+1):
            arr[j][k] = min(arr[j][k], arr[j][i]+arr[i][k])

sum = 0
for i in range(1, n+1):
    sum = max(arr[i][x]+arr[x][i], sum)

print(sum)

다익스트라로 다시 짜야겠어요...

다익스트라 for문? 방식으로 한 코드 입니당

import sys
input = sys.stdin.readline
n, m, x = map(int,input().split())

INF = int(1e9) #10억
arr = [[INF for j in range(n+1)] for i in range(n+1)]
graph = [[] for i in range(n+1)]
for i in range(1,m+1):
    start, end, cost = map(int, input().split())
    graph[start].append((end, cost))

def get_smallest_node(distance, visited):
    minValue = INF
    idx = 0
    for i in range(1, n+1):
        if distance[i] < minValue and not visited[i]:
            minValue = distance[i]
            idx = i
    return idx

def dijkstra(start, end):
    distance = [INF] * (n + 1)
    distance[start] = 0
    visited = [False] *(n+1)
    visited[start] = True
    for i in graph[start]:
        distance[i[0]] = i[1]
    for i in range(n-1):
        now = get_smallest_node(distance, visited)
        visited[now] = True
        for j in graph[now]:
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost
    return distance[end]

sum = 0
for i in range(1, n+1):
    a = dijkstra(i, x)
    b = dijkstra(x, i)
    sum = max(sum, a + b)

print(sum)

다익스트라로 하는 방법이 두갠데 하나는 for문으로? 하는 방법이래요 근데 지금 읽었는데 이 방법은 
전체 노드가 5000개 이하일 때 쓰는거고 10000개 이상이면 개선된 다익스트라 알고리즘을 사용해야한대요
왠지 시간초과 나오더라구요
다른 방법이 heapq이용해서 하는건데

import sys
import heapq
input = sys.stdin.readline
n, m, x = map(int,input().split())

INF = int(1e9) #10억
arr = [[INF for j in range(n+1)] for i in range(n+1)]
graph = [[] for i in range(n+1)]
for i in range(1,m+1):
    start, end, cost = map(int, input().split())
    graph[start].append((end, cost))
x

def dijkstra(start, end):
    q = []
    heapq.heappush(q, (0, start))
    distance = [INF] * (n+1)
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance[end]

sum = 0
for i in range(1, n+1):
    a = dijkstra(i, x)
    b = dijkstra(x, i)
    sum = max(sum, a + b)

print(sum)

오늘 어쩌다보니 플로이드워셜이랑 다익스트라 방법 두개 다로 해봤네요...레죤두...담에 다익스트라 재도전 해봐야겠어요

감동 ㅠ ㅠ