다익스트라 백준 1238번 파티

문제를 찾아보면 알겠지만 N개의 마을에 사는 N명의 학생들이 특정한 한 집에 모여 파티를 하고, 다시 집으로 돌아가는데 드는 비용 중 최대 비용을 구하는 것이다.

다익스트라 코드는 기본적인 코드이며,

우선 특정한 한 집(코드에서는 x)에서 각각 학생들의 집까지 거리를 구하기 위해 start를 x로 하고 다익스트라를 통해 최소신장트리를 구한다.

그리고 배열 하나를 만들어서 x마을부터 각 학생들의 집(1,2,...,N)까지의 최소거리를 더한다.

다시 for문을 반복하여 각각의 학생들(i번째 학생들)에 대해 다익스트라를 실행 한 뒤, 특정한 집(변수 x)에 도달하기까지 걸리는 최소비용을 구해서 배열에 더해준다.

최소비용중 최대를 구해야하므로 변수 res를 하나 두어 최대를 뽑아낸다.

---

res를 처음에 0으로 초기화 안해주어서 틀렸다.. 다음부터는 조심하자ㅜ(max비교를 위해선 res값 초기화가 필요하기 때문)

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

const int INF = 987654321;
int n, m,x;
int s,e, cost;
int dist[1010],ans[1010];
vector<pair<int,int>> v[1010];

void dijk(int start) {
	// memset(dist, 127, sizeof(dist)); // 127은 비트연산으로 약 21억 숫자
	// or
	fill(dist, dist + 1010, INF);

	// 시작 노드 초기화
	dist[start] = 0;

	// (가중치, 도착노드)
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,start });

	while (!pq.empty()) {
		int idx = pq.top().second;
		int cost = pq.top().first;
		pq.pop();

		// if (dist[idx] != cost) continue;

		for (int i = 0; i < v[idx].size(); i++) {
			int next = v[idx][i].first;
			int weight = v[idx][i].second;

			if (dist[next] > dist[idx] + weight) {
				// if u -> v , dist[v] < dist[u] + w(u,v)이면 초기화할 필요 x
				dist[next] = dist[idx] + weight;
				pq.push({ dist[next],next });
			}
		}
	}
}

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

	int res = 0;

	cin >> n >> m >> x;
	for (int i = 0; i < m; i++) {
		cin >> s >> e >> cost;
		v[s].push_back(make_pair(e, cost));
	}

	dijk(x); // x번 마을에서 모인 학생들이 집으로 가는데 필요한 최소비용 검사
	for (int i = 1; i <= n; i++) {
		
		ans[i] += dist[i]; // 1번 학생부터 
	}

	for (int i = 1; i <= n; i++) {
		if (i == x) continue;
		dijk(i); // 1번 학생부터 조사
		ans[i] += dist[x]; // x번 마을까지 가는데 필요한 최소비용
		res = max(res, ans[i]);
	}

	cout << res;
	return 0;
}