백준 1238번 파티 문제풀이(C++)

백준 1238번 파티

아이디어

마을이 도로로 이어져 있다 --> 그래프

시작점과 끝점이 같은 도로는 없으며 --> 싸이클이 존재하지 않는다

최단 시간에 오고 가기를 원한다 --> 다익스트라 알고리즘 사용

N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생 --> N명의 학생의 시간 다 확인

문제 해결

#include<bits/stdc++.h>
using namespace std;
// N의 최대값
#define MAX 1005
// int형 최대값을 MAX로 설정
#define INF 2147483647
// 그래프 v
vector<pair<int, int>> v[MAX];
int n, m, x;
int dijkstra(int start, int end) {
	int dist[MAX] = {0, };
	fill(&dist[0], &dist[0] + MAX, INF);
	dist[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (start != x && cur == end) {
        // 집에 갔다가 다시 돌아오는 것을 재귀로 확인
			return dist[end] + dijkstra(end, start);
		}
		if (dist[cur] < cost) continue;
		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i].first;
			int ncost = v[cur][i].second;
			if (cost + ncost < dist[next]) {
				dist[next] = cost + ncost;
				pq.push({ -dist[next], next });
			}
		}
	}
	return dist[end];
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> x;
	for (int i = 0; i < m; i++) {
		int start, end, _time; cin >> start >> end >> _time;
		v[start].push_back({ end, _time });
	}
	int _max = 0;
	for (int i = 1; i <= n; i++) {
		if (i == x)continue;
		_max = max(dijkstra(i, x), _max);
	}
	cout << _max << '\n';
	return 0;
}