[C++] 백준 1238: 파티

문제

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

1238번: 파티

 

해결방법

다익스트라 알고리즘으로 풀 수 있다.

1. 1부터 N까지 각 노드를 출발지로 하는 최단거리를 구한 후, X를 목적지로 하는 최단 거리를 배열에 저장한다.
2. X를 출발지로 하고 1부터 N까지의 최단 거리를 구한 후, 1에서 구한 배열에 더해준다.
3. 배열에 각 인덱스에 저장된 값은 노드 ->  X + X -> 노드 값이다. 따라서 가장 큰 값을 출력해주면 된다.

 

코드

#include<iostream>
#include<vector>
#include<queue>
#define INF 1e9 

using namespace std;

int n, m, x;
vector<pair<int, int>>graph[1001];
int d[1001];
int reverse_d[1001];

void dijkstra(int start) {
	fill_n(d, 1001, INF);
	priority_queue<pair<int, int>>pq;

	pq.push({ 0,start });
	d[start] = 0;

	while (!pq.empty()) {
		int dist = -pq.top().first;
		int now = pq.top().second;
		pq.pop();

		if (d[now] < dist)
			continue;

		for (int i = 0; i < graph[now].size(); i++) {
			int cost = dist + graph[now][i].second;

			if (cost < d[graph[now][i].first]) {
				d[graph[now][i].first] = cost;
				pq.push({ -cost,graph[now][i].first });
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> x;

	for (int i = 0; i < m; i++) {
		int a, b, t;
		cin >> a >> b >> t;
		graph[a].push_back({ b,t });
	}

	for (int i = 1; i <= n; i++) {
		dijkstra(i);

		reverse_d[i] = d[x];
	}

	dijkstra(x);

	int max = 0;
	for (int i = 1; i <= n; i++) {
		reverse_d[i] += d[i];
		if (reverse_d[i] > max)
			max = reverse_d[i];
	}

	cout << max;

	return 0;
}