[BOJ/Gold 2] 백준 19701 소 운전한다.(C++)

문제 링크

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

19701번: 소 운전한다.

 

문제

소들은 날아다니는 대신 그냥 운전을 하기로 했다. 소들이 사는 대한민국에는 도시가 V개 있고, 두 도시를 양방향으로 잇는 고속도로가 E개 있다. 물론 소들은 선린인터넷고가 있는 1번 도시에 산다. 아, 이건 꿀팁인데, 모든 고속도로의 가운데에는 돈까스를 파는 휴게소가 하나씩 있다.

이제 휴가철이 되어서 소들이 여행을 떠난다. 여러분도 알다시피, 암소 베시는 다른 도시로 여행을 떠나려 한다. 베시는 고속도로들을 적절히 타고 이동해서 목적지에 도착할 것이다. 이 때, 경로를 잘 골라서 1번 도시에서 베시가 여행갈 도시까지 가는 데에 걸리는 시간의 최솟값을 구하라. 아, 어떤 도시로 여행갈 지는 비밀이다. 그러니 2번에서 N번까지의 각각의 도시에 대해, 1번 도시에서 이 도시로 가는 데 걸리는 시간의 최솟값을 구하라.

... 그러나 베시는 문득 공허함을 느낀다. 베시는 이 문제가 '다익스트라 알고리즘'(Dijkstra algorithm)으로 너무 쉽게 풀린다는 사실도 알았을 뿐더러, 고속도로의 휴게소에서 파는 돈까스를 먹고 싶은 자신의 속마음을 알게 되었다. 베시는 모든 고속도로에 있는 돈까스를 모두 조사해, 돈까스의 맛을 수치화해 적어두었다. 베시는 휴가를 가는 경로에 있는 휴게소 가운데 정확히 한 곳에 들러서 돈까스를 사 먹을 것이다. 베시가 여행갈 수 있는 2번에서 N번까지의 각 도시에 대해, 경로와 들를 휴게소를 잘 골라서 1번 도시에서 이 도시로 가는 데 걸리는 시간에서 가는 도중에 휴게소를 적절히 하나 들러서 먹는 돈까스의 맛을 뺀 값의 최솟값을 구하라. 물론, 돈까스를 먹는 시간은 가는 데 걸리는 시간에 포함하지 않는다.

입력

첫째 줄에는 대한민국에 있는 도시의 개수 V와 고속도로의 개수 E가 주어진다.

둘째 줄부터 E개의 줄에는 각각의 고속도로의 정보가 주어진다. 각 줄에는, 고속도로가 잇고 있는 두 도시 x, y, x에서 y로 가는 데 걸리는 시간 t, 휴게소에서 파는 돈까스의 맛을 나타내는 값 k가 차례대로 공백을 사이에 두고 주어진다.

같은 두 도시 쌍을 잇는 고속도로가 두 개 이상 있는 경우는 없다. 모든 도시들은 고속도로를 이용해 직, 간접적으로 연결되어 있다.

출력

총 V-1개의 정수를 한 줄에 하나씩 출력한다. i번째로 출력하는 정수는, 1번 도시에서 i+1번 도시에서 가는 데에 걸리는 시간에서 가는 도중에 먹는 돈까스의 맛을 뺀 값의 최솟값이다.

제한

•  1≤V≤100,000
•  1≤E≤100,000
•  1≤x≠y≤V
•  1≤t≤20,000
•  1≤k≤1,000,000,000

예제 입력 1

4 5
1 2 2 1
2 3 3 2
2 4 4 3
1 3 6 2
4 3 3 4

예제 출력 1

1
3
3

1번 도시에서 2번 도시로 가고 싶다면, 첫 번째 고속도로를 타고 곧바로 갈 수 있다. 이 고속도로의 길이는 2이고, 이 고속도로에 있는 휴게소의 돈까스의 맛은 1이므로, 이 경로로 이동한다면, 문제에서 구하는 값은 2-1=1이다.

1번 도시에서 3번 도시로 가고 싶다면, 최적의 경로는 2번 도시를 경유해서 가는 것이다. 고속도로 두 개를 이용하게 되며, 경로의 전체 길이는 2+3=5이다. 두 고속도로에서 파는 돈까스의 맛은 각각 1과 2이므로, 둘 중 맛이 2인 돈까스를 사 먹는 것이 이득이다(돈까스는 한 번만 먹을 수 있음에 유의하라). 따라서 이 경로로 이동한다면, 문제에서 구하는 값은 5-2=3이다. 물론, 1번 도시에서 3번 도시로 직접 가는 고속도로를 이용할 수도 있겠지만, 그 고속도로를 이용한다면 문제에서 구하는 값이 6-2=4가 되므로, 최소가 아니다.

마찬가지로, 1번 도시에서 4번 도시로 가고 싶다면, 최적의 도시는 2번 도시를 경유해서 가는 것이다. 이 때에 문제에서 구하는 값은 6-3=3이 된다.

예제 입력 2

4 4
1 2 4 10
1 3 4 2
2 4 4 3
3 4 4 1

예제 출력 2

-6
2
-2

1번 도시에서 3번 도시로 가고 싶다면, 최적의 경로는 1번 도시에서 출발하여 1→2→1→3으로 가는 것이다. 1번 도시에서 2번 도시로 가는 고속도로에 있는 돈까스가 너무도 맛있기 때문에, 이렇게 경로를 틀어서라도 먹고 가는 것이 이득이다. 이 때에 문제에서 구하는 값은 12-10=2이다. 같은 정점을 여러 번 반복해서 방문해도 괜찮다는 점에 주목하라.

알고리즘 분류

• 최단 거리 알고리즘

풀이

최단 거리를 기록하는 2차원 배열 Cost[A][B]를 선언한다. 이것은 A지점까지 왔을 때의 최단 거리와 먹은 돈까스의 맛의 차이를 의미하며, B가 0이면 돈까스를 먹었다는 뜻이고, 1이면 돈까스를 안 먹었다는 뜻이다.

이제 1번 도시를 시작점으로 하는 다익스트라를 1회 수행하여, 돈까스를 먹은 경우와 안 먹은 경우 2가지를 따져서 최단 거리를 기록하면 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e11

using namespace std;
struct INFO {
	LL Dest, Cost, Eat;
};

struct INFO2 {
	LL Cost, Eat, Here;
};

struct COMP {
	bool operator()(INFO2 A, INFO2 B) {
		return (A.Cost > B.Cost);
	}
};

LL V, E;
vector<INFO> Edge[MAX];
LL Prev[MAX];
LL Cost[MAX][2];

void Input() {
	cin >> V >> E;
	for (int i = 1; i <= V; i++) {
		Cost[i][0] = INF;
		Cost[i][1] = INF;
	}
	for (int i = 0; i < E; i++) {
		int X, Y, T, K;
		cin >> X >> Y >> T >> K;
		Edge[X].push_back({ Y,T,K });
		Edge[Y].push_back({ X,T,K });
	}
}

void Dijkstra() {
	priority_queue<INFO2, vector<INFO2>, COMP> PQ;
	Cost[1][1] = 0;
	PQ.push({ 0,1,1 });

	while (!PQ.empty()) {
		LL CurCost = PQ.top().Cost;
		LL CurEat = PQ.top().Eat;
		LL CurX = PQ.top().Here;
		PQ.pop();

		if (Cost[CurX][CurEat] < CurCost) {
			continue;
		}

		for (int i = 0; i < Edge[CurX].size(); i++) {
			LL nextCost = Edge[CurX][i].Cost;
			LL nextX = Edge[CurX][i].Dest;
			LL nextEat = Edge[CurX][i].Eat;

			// 돈까스를 먹는다
			if (CurEat == 1) {
				if (Cost[nextX][0] > CurCost + nextCost - nextEat) {
					Cost[nextX][0] = CurCost + nextCost - nextEat;
					PQ.push({ Cost[nextX][0],0,nextX });
				}
			}

			// 돈까스를 안 먹는다
			if (Cost[nextX][CurEat] > CurCost + nextCost) {
				Cost[nextX][CurEat] = CurCost + nextCost;
				PQ.push({ Cost[nextX][CurEat],CurEat,nextX });
			}
		}
	};
}

void Find_Answer() {
	for (LL i = 2; i <= V; i++) {
		cout << min(Cost[i][0], Cost[i][1]) << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Dijkstra();
	Find_Answer();

	return 0;
}