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

문제 링크: https://www.acmicpc.net/problem/1238

1238번: 파티

1. 주의할 점

- 초기화를 잘 한다

- 다익스트라 알고리즘을 통해 최단거리를 구한다

- 파티로 가는, 그리고 나가는 거리의 최단거리를 구하기 위해 그래프의 방향이 반대인것도 구해서 벡터 V[][]에 저장한다

 

2. 구현

- 입력받은 단방향 그래프: 파티 -> 집으로 갈때의 최단거리

- 입력받은 단방향 그래프에서 방향을 반대로: 집 -> 파티까지의 최단거리

- 입력받을 때 단방향그래프는 V[][0]에, 반대방향 그래프는 V[][1]에 저장한다

- 다익스트라 알고리즘을 통해 파티장에서 각자의 집까지의 최단거리를 구해서 Result[][]에 저장한다(정방향, 역방향 모두)

- Result[][0] + Result[][1]의 값이 가장 큰 값을 출력한다

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
struct info {
	int idx, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
int node, edge, party, s, e, val;
vector<info> v[1001][2];
int result[1001][2];

void dijkstra(int cnt) {
	priority_queue<info, vector<info>, cmp> pq;
	tmp.idx = party;
	tmp.val = 0;
	pq.push(tmp);
	result[party][cnt] = 0;
	while (!pq.empty()) {
		int cidx = pq.top().idx;
		int cv = pq.top().val;
		pq.pop();
		if (result[cidx][cnt] < cv) continue;
		for (int i = 0; i < v[cidx][cnt].size(); i++) {
			int next = v[cidx][cnt][i].idx;
			int nv = v[cidx][cnt][i].val;
			if (result[next][cnt] > cv + nv) {
				result[next][cnt] = cv + nv;
				tmp.idx = next;
				tmp.val = cv + nv;
				pq.push(tmp);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge >> party;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		
		tmp.idx = e;
		tmp.val = val;
		v[s][0].push_back(tmp);
		tmp.idx = s;
		v[e][1].push_back(tmp);
	}
	for (int i = 1; i <= node; i++) {
		result[i][0] = INT_MAX;
		result[i][1] = INT_MAX;
	}
	dijkstra(0);
	dijkstra(1);
	int maxi = 0;
	for (int i = 1; i <= node; i++) 
		maxi = max(maxi, result[i][0] + result[i][1]);
	cout << maxi;
	return 0;
}