[BOJ]백준 23030번: 후다닥을 이겨 츄르를 받자!(C++)/Dijkstra

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

23030번: 후다다닥을 이겨 츄르를 받자!

좌표가 아닌 지하철 (노선, 역)의 정보를 가진 다익스트라 문제 유형

실제 그래프에 더 가까우니까 사실 다익스트라의 취지(?)에 더 적합한 문제 유형 같당

노선의 역 개수를 입력받아 이차원 벡터를 만들어준 뒤 환승역이 있는 곳에는 이어지는 역에 대한 정보를 넣어주었다

역 사이의 거리는 일정하므로 역 번호의 차를 이용했고

다익스트라 풀이를 위해 해당 노선에 존재하는 환승역들에 대해 탐색을 진행한 뒤 목적지가 같은 노선에 있다면 추가로 우선순위 큐에 넣어주었다(실제 가는 것 보다 환승이 더 빠를 수 있으므로)

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define pii pair<int,int>
#define pip pair<int,pii>
#define INF 987654321
using namespace std;

vector<vector<pii>> ds;
vector<vector<int>> ts;
vector<int> stationNum;
int n, m, t, k;

int main() {
	scanf("%d", &n);
	ds = vector<vector<pii>>(n + 1);
	ts = vector<vector<int>>(n + 1);
	stationNum = vector<int>(n + 1);
	for (int i = 1, s; i <= n; i++) {
		scanf("%d", &stationNum[i]);
		ds[i] = vector<pii>(stationNum[i]+1);
	}
	scanf("%d", &m);
	for (int i = 0,p1,p2,q1,q2; i < m; i++) {
		scanf("%d%d%d%d", &p1, &p2, &q1, &q2);
		ts[p1].push_back(p2);
		ts[q1].push_back(q2);
		ds[p1][p2] = make_pair(q1, q2);
		ds[q1][q2] = make_pair(p1, p2);
	}

	scanf("%d", &k);
	while (k--) {
		int u1, u2, v1, v2;

		scanf("%d%d%d%d%d", &t, &u1, &u2, &v1, &v2);

		vector<vector<int>> dist(n + 1);
		priority_queue<pip> pq;
		for (int i = 1; i <= n; i++) {
			dist[i] = vector<int>(stationNum[i]+1, INF);
		}

		pq.push(make_pair(0, make_pair(u1, u2)));
		dist[u1][u2] = 0;

		while (!pq.empty()) {
			int cost = -pq.top().first;
			auto cur = pq.top().second; pq.pop();
			if (cost > dist[cur.first][cur.second])continue;

			for (auto x : ts[cur.first]) {
				auto des = ds[cur.first][x];
				if (dist[des.first][des.second] > dist[cur.first][cur.second] + abs(cur.second - x) + t) {
					dist[des.first][des.second] = dist[cur.first][cur.second] + abs(cur.second - x) + t;
					pq.push(make_pair(-dist[des.first][des.second], des));
				}
			}
			if (cur.first == v1) {
				if (dist[cur.first][v2] > dist[cur.first][cur.second] + abs(cur.second - v2)) {
					dist[cur.first][v2] = dist[cur.first][cur.second] + abs(cur.second - v2);
					pq.push(make_pair(-dist[cur.first][v2], make_pair(cur.first, v2)));
				}
			}

		}

		printf("%d\n", dist[v1][v2]);
	}

	return 0;
}