[BOJ/C++]1238(파티)

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

• 사실 아이디어를 생각하기까지 4시간은 걸린 것 같습니다. 다익스트라 알고리즘이라는 발상은 바로 떠올랐지만 세세한 구현을 어떻게 처리할지 머릿속에서 고민만 몇 시간을..
• 개인적으로 이렇게 pair 써서 풀어야 되는 문제는 #define NODE first 와 같이 쓰는 걸 좋아하나.. 주먹구구식으로 그냥 풀다 보니 꽉 막힌 풀이가 되어버렸습니다.

1. 최단 시간에 오고 가기를 원함 ->그래프상에서 최단 경로이므로 다익스트라
2. 시작 경로가 조금 모호하다. 그래서 역으로 목적지를 시점으로 한 번, 각 노드에서 한 번씩 시도하여 왕복 최단 거리를 탐색

사실 이 분 코드가 좀 야무집니다.. 문제 풀고 보니 이 분이 푸신 2번 풀이(최적화 풀이)는 한 번쯤 보고 가시면 좋을 것 같아 남기고 갑니다.
Link: https://hyeo-noo.tistory.com/138

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 1001
#define INF 2147483647
#define p pair<int, int>
int n, m, x;
vector<p> path[MAX];	//dst, cost
int dist1[MAX], dist2[MAX];

void input() {
	cin >> n >> m >> x;
	int src, dst, cost;
	for (int i = 0; i < m; ++i) {
		cin >> src >> dst >> cost;
		path[src].push_back(make_pair(dst, cost));
	}
}

void dijkstra(int cur) {
	for (int i = 1; i <= n; ++i) {
		dist1[i] = INF;
	}
	priority_queue<p> pq;
	pq.push(make_pair(0, cur));
	dist1[cur] = 0;
	while (!pq.empty()) {
		int curDist = -pq.top().first;
		int curNode = pq.top().second;
		pq.pop();
		if (curDist > dist1[curNode]) continue;
		for (p i : path[curNode]) {
			int nxtDist = i.second + curDist;
			int nxtNode = i.first;
			if (nxtDist < dist1[nxtNode]) {
				dist1[nxtNode] = nxtDist;
				pq.push(make_pair(-nxtDist, nxtNode));
			}
		}
	}

}

void solution() {
	int answer = 0;
	input();
	for (int i = 1; i <= n; ++i) {
		dijkstra(i);
		dist2[i] = dist1[x];
	}
	dijkstra(x);
	for (int i = 1; i <= n; ++i) {
		int val = dist1[i] + dist2[i];
		if (answer < val) answer = val;
	}
	cout << answer;
}

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