백준 15422(Bumped!)

jh Seo·2023년 6월 5일
다익스트라 알고리즘백준한번에 푼 문제
0

백준

목록 보기
165/180

개요

백준 15422번: Bumped!
입력
The input consists of a single test case. The first line lists five space-separated integers n, m, f, s, and t, denoting the number of cities n (0 < n ≤ 50 000), the number of roads m (0 ≤ m ≤ 150 000), the number of flights f (0 ≤ f ≤ 1 000), the number s (0 ≤ s < n) of the city in which Peter’s trip starts, and the number t (0 ≤ t < n) of the city Peter is trying to travel to. (Cities are numbered from 0 to n − 1.)

The first line is followed by m lines, each describing one road. A road description contains three space separated integers i, j, and c (0 ≤ i, j < n, i ≠ j and 0 < c ≤ 50 000), indicating there is a road connecting cities i and j that costs c cents to travel. Roads can be used in either direction for the same cost. All road descriptions are unique.

Each of the following f lines contains a description of an available flight, which consists of two space separated integers u and v (0 ≤ u, v < n, u ≠ v) denoting that a flight from city u to city v is available (though not from v to u unless listed elsewhere). All flight descriptions are unique.

출력
Output the minimum number of cents Peter needs to spend to get from his home town to the competition, using at most one flight. You may assume that there is a route on which Peter can reach his destination.

접근 방식

다익스트라를 m번 돌리는 방식

  1. 다익스트라 알고리즘을 한번 사용해서 차를 타고
    s에서 t까지 가는 최소비용을 계산한다.

  2. 그 후, 각 비행루트의 시작점까지의 최소비용 + 비행루트 끝지점에서 목적지까지 다익스트라 알고리즘을 실행한 값을 다 구한다.
    그 값들의 최소값이 한번 비행기 탔을때의 최소비용이다.

  3. 그 후, 차만 타고가는 방식과 한번 비행기 탔을때의 최소비용을
    비교해서 더 작은 값을 출력한다.

2차원 배열을 사용해서 풀기

  1. 하지만 m이 1000으로 비교적 작은 수라 다익스트라를 m만큼 시행해도 시간초과가 안나오는거라고 생각이 들어서 더 효율적인 방법을 검색했다.

  2. 예전에 푼 문제인 백준 2206: 벽부수고 이동하기
    문제와 유사하게 풀면 다익스트라를 m번 안돌려도 된다.

  3. 기본적으로 2차원배열인 dist배열을 선언 후,
    행값이 0이라면 비행기를 안탄 상태, 1이라면 비행기를 탄 상태로 정의 된다.

  4. 기본 간선값들은 0번 행과 1번 행 모두 저장해준다.
    단 1번 행은 최대값 MAX를 더한 채로 저장해야한다.
    다익스트라에서 행을 구별하기 위함이다.

    	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v>>w;
		adj[0][u].push_back({ v,w });
		adj[0][v].push_back({ u,w });
		adj[1][u].push_back({ MAX + v,w });
		adj[1][v].push_back({ MAX + u ,w});
	}
	for (int i = 0; i < f; i++) {
		int u, v;
		cin >> u >> v;
		//비행기를 탄다면 이제 도착지점을 MAX더해줘서 1로 올리기
		adj[0][u].push_back({ MAX + v, 0});
	}

  5. 위코드에서 비행기간선은 dist배열의 0번 행에 MAX더한채로 저장을 한다.

  6. 그 후 우선순위 큐를 이용해, 노드값을 Max* 행 + 열 이렇게 저장해 사용한다.

    		void Solution() {
			fill(dist[0], dist[0] + n, INF);
			fill(dist[1], dist[1] + n, INF);
			dist[0][s] = 0;
			//first는 거리, second는 노드
			pq.push({ 0,s });

			while (!pq.empty()) {
				//k값은 dist의 행에 해당하고, curNode는 dist의 열에 해당한다.
				int curNode=0, k=0;

				do {
					curNode = pq.top().second % MAX;
					k = pq.top().second / MAX;
					pq.pop();
				} while (!pq.empty() && visited[k][curNode]);

				if (visited[k][curNode]) break;
				visited[k][curNode] = true;

				//adj[k][curNode]과 연결된 간선들에 대해서 
				for (auto& elem : adj[k][curNode]) {
					//nextK는 연결된 지점의 행값, nextNode는 연결된 지점의 열값, nextDist는 curNode와 nextNode사이 거리
					long long nextNode = elem.first % MAX, nextK = elem.first / MAX, nextDist = elem.second;

					if ( dist[nextK][nextNode] > dist[k][curNode] + nextDist) {
						dist[nextK][nextNode] = dist[k][curNode] + nextDist;
						//노드값을 저장할 때,max값을 곱해준후 저장한다.
						pq.push({dist[nextK][nextNode],nextK * MAX + nextNode});
					}
				}
			}
			//그냥 차타고갔을때( dist[0][e]), 비행기 탔을때 최소비용(dist[1][e])둘을 비교해서 최소값 출력
			cout << min(dist[0][e], dist[1][e]);
		}

  7. 행이 1이라면 MAX로 나눴을 때, 1이 나오고 0이라면 행값은 0이 되는 구조로, 처음엔 무조건 행이 0값으로 진행한다.
    진행하다가 비행기 루트들의 출발지점에서 진행방향이 갈리게 되는데
    비행기 간선을 타게되면 nextNode에 MAX값이 더해져서 저장되므로
    우선순위 큐에서 해당 노드를 꺼내고 행을 MAX로 나누면 1이 나오므로 비행기를 탄 후의 간선으로 진행이 된다.

다익스트라 m번 돌리는 코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int n, m, f, s, t;
//비행기를 안 타고 차로만 갔을때의 최소 비용 저장용 배열
long long originMinCost[150'001];
//비행기를 탔을때의 최소비용 저장용 배열
long long flightEndMinCost[150'001];
bool visited[150'001];
long long INF = 8'000'000'000;
vector<vector<pair<int,int>>> edge;
vector<pair<int,int>> flight;
priority_queue < pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
void Input() {
	int u, v, c;
	cin >> n >> m >> f >> s >> t;
	edge.resize(n);
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> c;
		edge[u].push_back({ v,c });
		edge[v].push_back({ u,c });
	}
	for (int i = 0; i < f; i++) {
		cin >> u >> v;
		flight.push_back({u,v});
	}
}
/// <summary>
/// 처음 시작점에서 나머지 노드들까지의 최단 거리구하기
/// </summary>
void FirstDeijkstra() {
	fill(visited, visited + 150'000, false);
	fill(originMinCost, originMinCost + 150'000, INF);

	originMinCost[s] = 0;
	pq.push({ originMinCost[s],s });
	while (!pq.empty()) {
		int curNode = 0;
		do {
			curNode = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visited[curNode]);
		if (visited[curNode]) break;
		visited[curNode] = true;

		for (auto& elem : edge[curNode]) {
			int nextNode = elem.first, nextDist = elem.second;
			if (originMinCost[nextNode] > originMinCost[curNode] + nextDist) {
				originMinCost[nextNode] = originMinCost[curNode] + nextDist;
				pq.push({originMinCost[nextNode],nextNode});
			}
		}
	}
}
/// <summary>
/// 모든 비행 루트에 대해 비행기를 탔을 때의 최소비용을 구하고 그 비용중 최솟값을 구하는 함수
/// </summary>
void DetermineFlight() {
	//모든 flight를 한번씩 탔을때 거리중의 제일 최소비용
	long long Ans = originMinCost[t];
	//각 flight의 루트에서 다익스트라를 실행해서 최소거리 찾기
	for (auto& elem : flight) {
		fill(flightEndMinCost, flightEndMinCost + 150'000, INF);
		fill(visited, visited + 150'000, false);
		//비행 도착점까지의 비용은 비행 출발점까지의 비용과 같다.
		flightEndMinCost[elem.second] = originMinCost[elem.first];
		//비행 도착점에서 목적지까지 다익스트라 
		pq.push({ flightEndMinCost[elem.second],elem.second });
		while (!pq.empty()) {
			int curNode = 0;
			do {
				curNode = pq.top().second;
				pq.pop();
			} while (!pq.empty() && visited[curNode]);

			if (visited[curNode]) break;
			visited[curNode] = true;

			for (auto& elem : edge[curNode]) {
				int nextNode = elem.first, nextDist = elem.second;
				if (flightEndMinCost[nextNode] > flightEndMinCost[curNode] + nextDist) {
					flightEndMinCost[nextNode] = flightEndMinCost[curNode] + nextDist;
					pq.push({ flightEndMinCost[nextNode],nextNode });
				}
			}
		}
		Ans = min(Ans, flightEndMinCost[t]);
	}
	cout << Ans;	
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
	FirstDeijkstra();
	DetermineFlight();
}

2차원 배열을 통해 푸는 코드

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

	const int MAX = 50000;
	const long long INF = 1e18;
	vector<pair<long long, long long>> adj[2][MAX];
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>> > pq;
	int n, m, f, s, e;
	long long dist[2][MAX];
	bool visited[2][MAX]={false,};

	void Input() {
		cin >> n >> m >> f >> s >> e;
		for (int i = 0; i < m; i++) {
			int u, v, w;
			cin >> u >> v>>w;
			adj[0][u].push_back({ v,w });
			adj[0][v].push_back({ u,w });
			adj[1][u].push_back({ MAX + v,w });
			adj[1][v].push_back({ MAX + u ,w});
		}
		for (int i = 0; i < f; i++) {
			int u, v;
			cin >> u >> v;
			//비행기를 탄다면 이제 도착지점을 MAX더해줘서 1로 올리기
			adj[0][u].push_back({ MAX + v, 0});
		}
	}
	void Solution() {
		fill(dist[0], dist[0] + n, INF);
		fill(dist[1], dist[1] + n, INF);
		dist[0][s] = 0;
		//first는 거리, second는 노드
		pq.push({ 0,s });

		while (!pq.empty()) {
			//k값은 dist의 행에 해당하고, curNode는 dist의 열에 해당한다.
			int curNode=0, k=0;

			do {
				curNode = pq.top().second % MAX;
				k = pq.top().second / MAX;
				pq.pop();
			} while (!pq.empty() && visited[k][curNode]);

			if (visited[k][curNode]) break;
			visited[k][curNode] = true;

			//adj[k][curNode]과 연결된 간선들에 대해서 
			for (auto& elem : adj[k][curNode]) {
				//nextK는 연결된 지점의 행값, nextNode는 연결된 지점의 열값, nextDist는 curNode와 nextNode사이 거리
				long long nextNode = elem.first % MAX, nextK = elem.first / MAX, nextDist = elem.second;

				if ( dist[nextK][nextNode] > dist[k][curNode] + nextDist) {
					dist[nextK][nextNode] = dist[k][curNode] + nextDist;
					//노드값을 저장할 때,max값을 곱해준후 저장한다.
					pq.push({dist[nextK][nextNode],nextK * MAX + nextNode});
				}
			}
		}
		//그냥 차타고갔을때( dist[0][e]), 비행기 탔을때 최소비용(dist[1][e])둘을 비교해서 최소값 출력
		cout << min(dist[0][e], dist[1][e]);
	}
	int main() {
		ios_base::sync_with_stdio(0);
		cin.tie(0);
		Input();
		Solution();
	}

문풀후생

예전에 푼 문제를 다시 보면서 기억을 떠올렸던 문제다.

profile
jh Seo
코딩 창고!
이전 포스트

백준 5719(거의 최단 경로)

다음 포스트

백준 1162(도로포장)

0개의 댓글