C++ / 백준 / 1238 / 파티

문제

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

1238번: 파티

문제풀

이

다익스트라 알고리즘으로 풀었다.

양방향이 아닌 단방향의 도로의 정보가 주어지므로 조심해야한다.

 

도로들의 정보를 입력받고, 다익스트라 알고리즘을 통해 최단 거리를 저장한다.

( min_time[town1][town2] = x라면 town1에서 town2로 x의 시간이 걸린다는 의미 )

반복문을 통해 N마을에서 X마을로 가는 시간, X마을에서 N마을로 가는 시간만 구해 최소 시간을 구한다.

 

우선순위큐는 {마을 번호, 건너는 시간}으로 두고, 시간 기준 오름차순으로 정렬하게 cmp를 작성했다.

 

 

코드

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

vector<vector<pair<int, int>>>road;
vector<vector<int>>min_time;
int N;

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

void Dijkstra(int start) {
	priority_queue<pair<int, int>,vector<pair<int, int>>, cmp>pq; // 노드,시간
	pq.push({start,0});
	int town(0), time(0), idx(0);
		
	pq.push({start, 0});
	
	while (!pq.empty()) {
		town = pq.top().first;
		time = pq.top().second;
		pq.pop();
		for (idx = 0; idx < road[town].size(); ++idx) {
			int next_town = road[town][idx].first;
			int next_time = road[town][idx].second;
			if (min_time[start][next_town] > next_time + time) {
				min_time[start][next_town] = next_time + time;
				pq.push({ next_town, next_time + time });
			}
		}
	}
}

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

	int M(0), X(0), idx(0),idx2(0), town1(0), town2(0), time(0), answer(0);
	cin >> N >> M >> X;

	road = vector<vector<pair<int, int>>>(N + 1);
	min_time = vector<vector<int>>(N + 1, vector<int>(N + 1, 99999999));

	for (idx = 0; idx < M; ++idx) {
		cin >> town1 >> town2 >> time;
		road[town1].push_back({ town2, time });
	}

	for (idx = 1; idx <= N; ++idx) {
		Dijkstra(idx);		
	}

	for (idx = 1; idx <= N; ++idx) {
		if (idx != X) {
			answer = max(answer, min_time[idx][X] + min_time[X][idx]);
		}
	}
	cout << answer;
}