[백준] 1238번 C++ 파티

 

풀이)

이 문제는 다익스트라 알고리즘을 이용하여 최단거리를 구하는 문제이다.

이때  학생이 x에 모인 후에 원래있던 곳으로 되돌아가는 거리까지를 추가하여 구해주면된다.

 

1번 마을(노드)에 있는 학생이 x번 까지 갔다가 1번 노드로 다시 돌아가야된다.

1- > x - > 1  여기서 1->x, x->1까지의 최단 거리를 구해준 후, 이 총 거리가 가장 긴 학생의 소요시간을 출력해주면 답이다.

 

 

코드)

#include<iostream>
#include<vector>
#include<queue>
#include<limits>
using namespace std;

int n, m, x;
vector<vector<pair<int, int>>> graph;
vector<int> dist;

const int INF = numeric_limits<int>::max();

int dijkstra(int start) {
	dist.assign(n + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	pq.push({ 0,start }); // 시간, 시작노드
	dist[start] = 0;  

	while (not pq.empty()){
		int current = pq.top().second;
		int distance = pq.top().first;

		pq.pop();

		if (dist[current] < distance) continue;

		for (const auto& a : graph[current]) {
			int nextnode = a.second;
			int nextvalue = a.first + distance;

			if (dist[nextnode] > nextvalue) {
				dist[nextnode] = nextvalue;
				pq.push({ nextvalue, nextnode });
			}
		}
	}

	return dist[x];
}

int dijkstra(int start, int end) {
	dist.assign(n + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	pq.push({ 0,start }); // 시간, 시작노드
	dist[start] = 0;

	while (not pq.empty()) {
		int current = pq.top().second;
		int distance = pq.top().first;

		pq.pop();

		if (dist[current] < distance) continue;

		for (const auto& a : graph[current]) {
			int nextnode = a.second;
			int nextvalue = a.first + distance;

			if (dist[nextnode] > nextvalue) {
				dist[nextnode] = nextvalue;
				pq.push({ nextvalue, nextnode });
			}
		}
	}

	return dist[end];
}






int main()
{
	cin >> n >> m >> x;

	graph.resize(n + 1);
	dist.assign(n + 1, INF);

	// n명의 학생, m개의 단방향도로, x마을에서 모이기로함..

	while (m--) {
		int u, v,value;
		cin >> u >> v >> value;

		graph[u].push_back({ value,v });
	}
	

	int  solve{};
	for (int i = 1; i <= n; ++i) {
		int tmp = dijkstra(i) +dijkstra(x, i);
		if (solve < tmp) solve = tmp;
	}

	cout << solve;


}