백준 1238번 파티 C++

출처 : https://www.acmicpc.net/problem/1238

 

다익스트라를 모든 점에서 돌리면서 각 점에서의 최단 거리를 저장해놓고 [n][x] + [x][n]중 가장 큰 값을 찾아서 출력하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

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

struct VertexCost {
	bool operator<(const VertexCost& other) const {
		return cost < other.cost;
	}
	bool operator>(const VertexCost& other) const {
		return cost > other.cost;
	}
	int vertex;
	int cost;
};

void Dijkstra(int start) {

	vector<int> best(n + 1, INT_MAX);
	priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;

	pq.push({ start,0 });
	best[start] = 0;

	while (!pq.empty()) {
		auto curr = pq.top();
		pq.pop();

		int vertex = curr.vertex;
		int cost = curr.cost;
		if (cost > best[vertex])
			continue;

		for (auto next : graph[vertex]) {
			int nextCost = cost + next.second;
			if (nextCost >= best[next.first])
				continue;

			best[next.first] = nextCost;
			pq.push({ next.first,nextCost });
		}
	}
	for (int i = 1; i <= n; i++) {
		dist[start][i] = best[i];
	}
}

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

	cin >> n >> m >> x;
	graph = vector<vector<pair<int, int>>>(n + 1, vector<pair<int, int>>());
	dist = vector<vector<int>>(n + 1, vector<int>(n + 1));
	for (int i = 0; i < m; i++) {
		int a, b, d;
		cin >> a >> b >> d;
		graph[a].push_back({ b,d });
	}
	for (int i = 1; i <= n; i++) {
		Dijkstra(i);
	}
	int maxDist = 0;
	for (int i = 1; i <= n; i++) {
		int sum = dist[i][x] + dist[x][i];
		maxDist = max(maxDist, sum);
	}
	cout << maxDist;
};