[백준 1238] 파티 (C++)

 

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 2147483646
using namespace std;
typedef pair<int, int>pii;

int V, E, K;
int distk[1001];
int dist[1001];
vector<pii> d[1001];     //그래프의 정보 담음
int visited[1001];
int max_distance = -1;
priority_queue< pii, vector<pii>, greater<pii> > pq;
// 아주 기본적인 다익스트라 

void dijkstra(int st) {
	dist[st] = 0;
	// { 거리 , 현재 vertex} 
	pq.push({ 0,st });

	while (!pq.empty()) {
		int curr = pq.top().second; // 방문한 vertex
		int currd = pq.top().first;
		visited[curr] = 1;
		pq.pop();
		// 이동후 정보 갱신
		for (auto i : d[curr]) {
			int next = i.first, nextd = i.second;
			if (dist[next] > currd + nextd && !visited[next]) {
				dist[next] = currd + nextd;
				pq.push({ dist[next], next });

			}
		}
	}

}

void clear() {
	while (!pq.empty())
	{
		pq.pop();
	}
	for (int i = 1; i <= V; i++) dist[i] = INF;
	for (int i = 0; i < 1001; i++) visited[i] = 0;
}

int main() {
	// V vertex의 개수 
	// Edge 의 개수 
	// K 시작 정점의 번호 
	FASTIO;
	cin >> V >> E >> K;
	for (int i = 0; i < E; i++) {
		//인접 그래프 생성
		int a, b, c; cin >> a >> b >> c;
		d[a].push_back({ b,c });  // {vertex , 거리}
	}
	clear();
	dijkstra(K);

	for (int i = 1; i <= V; i++) {
		distk[i] = dist[i];
	}
	for (int i = 1; i <= V; i++) {
		if (i == K)
			continue;
		else {
			clear();
			dijkstra(i);
			if (max_distance <= dist[K] + distk[i])
				max_distance = dist[K] + distk[i];
			//cout << max_distance << "\n";
		}
	}

	cout<< max_distance;

}

Vertex의 개수가 1000개이므로 플로이드 대신 다익스트라를 사용해야 한다고 판단했다.

 

일단 최종 경로를 기준으로 다익스트라를 한번 돌린 후

이후에는 한곳씩 다익스트라를 돌려가며 최대값을 저장했다.