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

 

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

 

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

1238번: 파티

---

 

 

해결전략

 

Dijkskra 다익스트라

 

---

 

정답 코드

 

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

int n, m, x; // n: 마을의 수(각각의 마을에 1명의 학생이 거주), m: 단방향 도로 수, x: 파티가 벌어지는 마을
vector<vector<pair<int, int>>> v(1001); // 각 마을 간의 도로 정보를 저장하는 벡터
int result[1001][1001]; // 각 마을 간의 최단 거리를 저장하는 배열

struct Edge{
	int city, cost;

	Edge(int a, int b){
		city = a;
		cost = b;
	}

	bool operator<(const Edge& e) const{
		return cost > e.cost;
	}
};

// 다익스트라 알고리즘을 구현한 함수: start에서 end까지의 최단 거리를 찾음
void D(int start, int end) // start: 시작 마을, end: 도착 마을
{
	priority_queue<Edge> pQ;
	pQ.push({ start, 0 }); // 시작 위치와 비용을 큐에 삽입

	vector<int> dist(n + 1, 2147000000); // 시작 위치로부터 각 도시까지의 최단 거리를 저장하는 벡터. 최대값으로 초기화
	dist[start] = 0; // 시작 위치는 비용이 0

	while (!pQ.empty())
	{
		int curCity = pQ.top().city;
		int curCost = pQ.top().cost;
		pQ.pop();

		if (curCity == end) // 도착
		{
			result[start][end] = dist[end]; // 최단 거리를 결과 배열에 저장
			break;
		}

		// 이미 더 짧은 경로가 있다면 넘어감
		if (dist[curCity] < curCost) continue; 

		// 아직 방문하지 않은 인접 도시 탐색
		for (int i = 0; i < v[curCity].size(); i++) 
		{
			int nextCity = v[curCity][i].first; // 다음 도시
			int nextCost = curCost + v[curCity][i].second; // 다음 도시까지의 비용

			if (dist[nextCity] > nextCost) // 더 적은시간이 걸리는 경로를 발견한 경우
			{
				dist[nextCity] = nextCost; // 해당 경로를 이동하는데 걸리는 비용(시간) 갱신
				pQ.push({ nextCity, nextCost });
			}
		}
	}
}

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

	cin >> n >> m >> x;
	int a, b, c;
	for(int i = 0; i < m; i++){
		cin >> a >> b >> c;
		v[a].push_back({ b, c });
	}

	// 파티가기
	for(int k = 1; k <= n; k++) // 시작 위치를 다르게해서 출발. 시작위치(k) -> 도착위치(x)
	{
		D(k, x);
	}
	// 파티 끝난후 집으로 돌아오기
	for (int k = 1; k <= n; k++) // 도착 위치를 다르게해서 출발. 시작위치(x) -> 도착위치(k)
	{
		D(x, k);
	}

	int answer = 0; // 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간
	for(int i = 1; i <= n; i++)
	{
		answer = max(answer, result[i][x] + result[x][i]); // 왕복 시간이 가장 긴 학생의 시간 계산
	}

	cout << answer;	

	return 0;
}

 

 

---