[C++] 백준 1238 : 파티

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

1238번: 파티

백준 1238번 파티 문제를 풀었다.

 

최단 경로 중에 가장 긴 경로를 구하는 문제다.

입력 N이 최대 1000개라서 플로이드 와샬 알고리즘은 사용할 수 없다.

간선의 가중치에 음수가 없어서 다익스트라 알고리즘을 사용했다.

 

X마을로 갔다가 다시 자신의 마을로 최단 경로를 통해서 돌아오고 이 값을 기록해야한다.

먼저 X마을로부터 다른 마을까지의 최단 경로를 다익스트라 알고리즘을 사용해서 구한다.

그 다음 첫 번째 마을부터 마지막 마을까지 반복문을 돌면서 각각의 최단 경로를 계산한다.

dist[i][x] + dist[x][i] 의 값은 i번 마을에서 x번 마을로 가는 최단경로와 x번 마을에서 i번 마을로 가는 최단경로를 더한 값이다.

max변수 하나를 설정해서 x마을에 오고 가는데 가장 비용이 친구의 소요시간을 저장하고 출력한다.

 

아래는 전체 코드입니다.

#pragma warning(disable:4996)
#include <iostream>
#include <string>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 100000000

struct compare {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.second > b.second;
	}
};

vector<pair<int, int>> adj[1001];
priority_queue < pair<int, int>, vector<pair<int, int>>, compare> pq;
vector<int> dist[1001];

void dijkstra(int n) {
	while (!pq.empty()) {
		int cur = pq.top().first;
		int cost = pq.top().second;
		pq.pop();
		for (int i = 0; i < adj[cur].size(); i++) {
			int next = adj[cur][i].first;
			int next_cost = cost + adj[cur][i].second;
			if (dist[n][next] > next_cost) {
				dist[n][next] = next_cost;
				pq.push({ next,next_cost });
			}
		}
	}
}

int main() {
	int n, m, x;
	cin >> n >> m >> x;
	
	int start, end, cost;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &start, &end, &cost);
		adj[start].push_back({ end,cost });
	}

	for (int i = 1; i <= n; i++) {
		dist[i].assign(n + 1, INF);
	}

	// Calculate the shortest path from X node to other nodes
	dist[x][x] = 0;
	pq.push({ x,dist[x][x] });
	dijkstra(x);


	int max = 0;
	int temp;
	for (int i = 1; i <= n; i++) {
		dist[i][i] = 0;
		pq.push({ i,dist[i][i] });
		dijkstra(i);
		temp = dist[i][x] + dist[x][i];
		if (max < temp)
			max = temp;
	}

	cout << max;

	return 0;
}