[BOJ] 1238번 파티 (C++)

문제 (https://www.acmicpc.net/problem/1238)

1238번: 파티

N개의 마을에는 각각 한 명의 학생이 살고 있고, 입력받은 X번 마을에서 파티가 열린다. 모든 학생들의 이동거리는 최단거리여야 한다.
N명의 학생들 중 (i번째 마을 -> x번 마을) + (x번 마을 -> i번째 마을) 시간이 가장 긴 학생의 소요시간을 출력하면 된다.

 

Dijkstra Algorithm: '한 정점'에서 '모든 정점'으로의 최단경로
인접 리스트를 활용하여 연결된 정점들의 정보를 저장해준다. 우선순위 큐를 사용하여 인접 노드들 중 거리가 가까운 노드부터 처리한다. 인접 노드를 거쳐서 가는 거리가 기존 거리보다 짧다면 해당 거리를 최단경로로 설정한다.

1. i에서 x로의 최단경로
   dijkstra 함수에 i값 (1 ~ n)을 인자로 각각 넣어주며 i에서 모든 정점으로의 최단경로를 dst배열에 넣어준다. 필요한 값은 i에서 x로 가는 거리이므로 n개의 dst[x] 값을 ans 배열에 순서대로 넣어준다.
2. x에서 i로의 최단경로
   dijkstra 함수에 x값을 인자로 넣어주고 x에서 모든 정점으로의 최단경로를 ans 배열 값에 더해준다.
   ans 배열 중 가장 큰 값을 답으로 출력한다.

---

[소스코드]

	/*
	BOJ 1238번: 파티
	2021-07-13
	*/
	#include <iostream>
	#include <queue>
	#include <algorithm>
	#define MAX 1001
	#define INF 1e9
	using namespace std;
	vector<pair<int, int>> graph[MAX];
	int dst[MAX], ans[MAX];
	int n, m, x, s, e, t;
	void dijkstra(int start){
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq; //거리, 노드
	pq.push(make_pair(0, start));
	dst[start] = 0;
	while(!pq.empty()){
	int cost = pq.top().first;
	int now = pq.top().second;
	pq.pop();
	for(int i = 0 ; i < graph[now].size() ; i++){
	int next = graph[now][i].first;
	int nCost = graph[now][i].second;
	if(cost+nCost < dst[next]){
	dst[next] = cost + nCost;
	pq.push(make_pair(cost + nCost, next));
	}
	}
	}
	}
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> x;
	for(int i = 1 ; i <= n ; i++){
	dst[i] = INF;
	}
	for(int i = 0 ; i < m ; i++){
	cin >> s >> e >> t;
	graph[s].push_back(make_pair(e, t));
	}
	//i to x
	for(int i = 1 ; i <= n ; i++){
	for(int j = 1 ; j <= n ; j++){
	dst[j] = INF;
	}
	dijkstra(i);
	ans[i] = dst[x];
	}
	for(int i = 1 ; i <= n ; i++) dst[i] = INF;
	// start x
	dijkstra(x);
	for(int i = 1 ; i <= n ; i++){
	ans[i] += dst[i];
	}
	cout << *max_element(ans+1, ans+n+1);
	return 0;
	}

view raw 1238.cpp hosted with ❤ by GitHub

---

2021-07-13

Gold 3

- 그래프 이론

- 다익스트라