백준 17833번, 홍익대학교 지하캠퍼스

 

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

17833번: 홍익대학교 지하캠퍼스

요약

 

지하 R층에서 지하 D층으로 이어지는 캠퍼스 모델을 설계한다.

---

1. 시작 지점 지하 R층과 도착지점 지하 D층이 주어지고, 사용할 수 있는 건물 모델들이 주어진다. 이때, 모델이 최종적으로 위치한 범위가 지하 1층부터 지하 N층을 만족한다면 자유롭게 건물을 배치할 수 있다.

 

2. 모델을 제작하는데 T의 시간이 걸리고, 건물을 좌우로 반전시켜 배치할 수 있으므로, 가중치가 T인 양방향 간선으로 생각할 수 있다. 건물을 범위 내에서 자유롭게 배치할 수 있으므로, 각 간선이 연결하는 두 정점은 $(E_{1} + j, E_{2} + j)   (0\leq j\leq N-H)$이다.

 

3. 위 그래프에서 다익스트라를 통해 정점 R에서 정점 D로 향하는 최단경로를 구한다. 

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<long, int> pli;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

struct cmp {
	bool operator() (pli A, pli B) {
		return A.first > B.first;
	}
};

int N, R, D, M;
vector <pli> graph[2001];
long long dist[2001];

void Dijkstra(int start);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> R >> D >> M;
	for (int i = 0; i < M; i++) {
		int H, E1, E2;
		long long T;
		cin >> H >> T >> E1 >> E2;
		for (int j = 0; j <= N - H; j++) {
			graph[E1 + j].push_back({ T, E2 + j });
			graph[E2 + j].push_back({ T, E1 + j });
		}
	}
	Dijkstra(R);
	if (dist[D] == INF) cout << -1;
	else cout << dist[D];
	return 0;
}

void Dijkstra(int start) {
	for (int i = 1; i <= N; i++) dist[i] = INF;
	priority_queue <pli, vector<pli>, cmp> pq;
	dist[start] = 0;
	pq.push({ 0, start });
	while (pq.size()) {
		int now = pq.top().second;
		long long val = pq.top().first;
		pq.pop();
		if (dist[now] < val) continue;
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].second;
			long long new_val = val + graph[now][i].first;
			if (dist[next] > new_val) {
				dist[next] = new_val;
				pq.push({ new_val, next });
			}
		}
	}
}