[백준] 1238번 파티 C++ 코드

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
// 단방향
const int INF = 987654321;
int n,m,x,s,e,t,visited[1003],res;
vector<pair<int,int>> adj[1003];

int dijkstra(int start, int end) {
	fill(visited, visited + 1003, INF);
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
	q.push({0, start});
	visited[start] = 0;
	while(!q.empty()) {
		int dist = q.top().first;
		int here = q.top().second;
		q.pop();
		if(here == end) return visited[end];
		if(dist > visited[here]) continue;
		for(pair<int,int> pa : adj[here]) {
			int cost = dist + pa.second;
			if(visited[pa.first] > cost) {
				visited[pa.first] = cost;
				q.push({cost, pa.first});
			}
		}
	}
}

int main() {
	cin >> n >> m >> x;
	for(int i = 0; i < m; i++) {
		cin >> s >> e >> t;
		adj[s].push_back(make_pair(e, t));
	}
	for(int i = 1; i < n + 1; i++) {
		int tmp = dijkstra(i, x) + dijkstra(x, i);
		res = max(res, tmp);		
	}
	cout << res << '\n';
	return 0;
}

풀이

가중치가 있는 최단거리를 구해야하므로 다익스트라 알고리즘을 선택했다. 그리고 집에서 파티장, 파티장에서 집까지 거리를 구하고 최대값을 비교해서 출력해주면 된다.