[백준/C++] 1238. 파티

문제 

www.acmicpc.net/problem/1238

1238번: 파티

풀이

모든 마을 친구들 i (1~N)에 대해서 

왕복 거리 = i 부터 X까지의 거리 + X부터 i까지의 거리 를 구한 후,

왕복 거리의 최댓값을 출력하면 되는 문제이다.  

 

다익스트라 알고리즘을 이용하여 모든 마을 ~ 모든 마을 까지의 최솟값을 구한 후 

왕복 거리의 최댓값을 구하면 된다. 

 

우선순위 큐를 이용한 다익스트라 알고리즘 구현에 꽤나 익숙해진 것 같다.

다만, 입력을 인접리스트로 받아야 한다는 사실을 기억해야 함..! 

 

+ fill()을 이용해 2차원 배열 채우는데, 인덱스 숫자를 잘못 적어서 매우 고생했다. 

1001칸 짜리 배열이면 인덱스가 1000까지라는걸 기억하자 왜 까먹은걸까..? 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define INF 987654321

vector<pair<int, int>> adjs[1001];
int min_route[1001][1001];
int N, M, X;

void Dijkstra(int start) {
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	min_route[start][start] = 0;

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (min_route[start][cur] < cost) continue;
		for (int i = 0;i < adjs[cur].size();i++) {
			int there = adjs[cur][i].first;
			int new_cost = cost + adjs[cur][i].second;
			if (new_cost < min_route[start][there]) {
				min_route[start][there] = new_cost;
				pq.push(make_pair(-new_cost,there));
			}
		}
	}
}
int main(void) {
	cin >> N >> M >> X;
	for (int i = 0;i < M;i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		adjs[start].push_back(make_pair(end, cost));
	}
	fill(&min_route[0][0], &min_route[1000][1001], INF);
	for (int start = 1;start <= N;start++) {
		Dijkstra(start);
	}
	int maxD = 0;
	for (int start = 1;start <= N;start++) {
		int cost = min_route[start][X] + min_route[X][start];
		maxD = max(maxD, cost);
	}
	cout << maxD << endl;
	return 0;
}

결과