[python] 백준 > 다익스트라 > 파티

[문제]

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

www.acmicpc.net/problem/1238

1238번: 파티

 

[나의 풀이]

import sys
import heapq
input = sys.stdin.readline
N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(M):
    s_node, e_node, cost = map(int, input().split())
    graph[s_node].append((e_node, cost))
def dijkstra(start, end):
    heap = []
    distance = [sys.maxsize] * (N + 1)
    heapq.heappush(heap, (0, start))
    distance[start] = 0
    while heap:
        h_cost, h_node = heapq.heappop(heap)
        for n, c in graph[h_node]:
            sum_cost = h_cost + c
            if distance[n] > sum_cost:
                distance[n] = sum_cost
                heapq.heappush(heap, (sum_cost, n))
    return distance[end]
result = []
for i in range(N):
    result.append(dijkstra(i+1, X)+dijkstra(X, i+1))
print(max(result))

 

 

[다른 사람의 풀이]

[python]

import sys
from heapq import heappush,heappop
input = sys.stdin.readline
N,M,X = map(int,input().split())
graph=[[] for _ in range(N+1)]
result=[]
for _ in range(M):
    s,e,t = map(int, input().split())
    graph[s].append((e,t))
def dijkstra(start,end):
    heap=[]
    heappush(heap,(0,start))
    distance = [sys.maxsize] * (N+1)
    distance[start] = 0
    while heap:
        weight,index = heappop(heap)
        for e,t in graph[index]:
            if distance[e] > weight+t:
                distance[e] = weight+t
                heappush(heap,(weight+t,e))
    return distance[end]
for i in range(N):
    result.append(dijkstra(i+1,X)+dijkstra(X,i+1))
print(max(result))

 

 

[C++]

#include <iostream>
#include <queue>
#include <math.h>
#include <cstring>
#define INF 123456789
using namespace std;
int arr[1002][1002];
int rearr[1002][1002];
int djistar[1002];
int redjistar[1002];
struct node {
	int time, vertex;
};
bool operator<(node a, node b) {
	return a.vertex > b.vertex;
}
priority_queue<node> pq;
node nd;
int main() {
	int n, m, x;
	int a, b, t;
	cin >> n >> m >> x;
	for (int i = 1; i <= n; i++) {
		memset(arr[i], -1, sizeof(arr[i]));
		memset(rearr[i], -1, sizeof(rearr[i]));
	}
	memset(djistar, INF, sizeof(djistar));
	memset(redjistar, INF, sizeof(redjistar));
	for (int j = 0; j < m; j++) {
		cin >> a >> b >> t;
		arr[a][b] = t;
		rearr[b][a] = t;
	}
	pq.push(node{ 0, x });
	djistar[x] = 0;
	//w(x -> all vertex)
	while (!pq.empty()) {
		nd = pq.top();
		pq.pop();
		for (int k = 1; k <= n; k++) {
			if (arr[nd.vertex][k] != -1) {
				if (nd.time + arr[nd.vertex][k] < djistar[k]) {
					djistar[k] = nd.time + arr[nd.vertex][k];
					pq.push(node{ djistar[k],k });
				}
			}
		}
	}
	pq.push(node{ 0, x });
	redjistar[x] = 0;
	//w(x -> all vertex)
	while (!pq.empty()) {
		nd = pq.top();
		pq.pop();
		for (int k = 1; k <= n; k++) {
			if (rearr[nd.vertex][k] != -1) {
				if (nd.time + rearr[nd.vertex][k] < redjistar[k]) {
					redjistar[k] = nd.time + rearr[nd.vertex][k];
					pq.push(node{ redjistar[k],k });
				}
			}
		}
	}
	int answer = 0;
	for (int l = 1; l <= n; l++) {
		answer = max(redjistar[l] + djistar[l], answer);
	}
	cout << answer<<"\n";
	system("pause");
	return 0;
}