취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7804번 문제인 Taxi!이다.
문제는 아래 링크를 확인하자.

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

문제의 주어진 상황은 (도착지점, 사용해야 하는 비용)의 쌍을 하나의 정점으로, 서로 이동할 수 있는 관계의 두 지점에 대하여 이동비용만큼 영향을 주는 관계(단, 총 사용 비용이 $r$ 이하)를 방향간선으로 하는 그래프로 모델링할 수 있다.

이 그래프 위에서의 최단거리를 구해 문제를 해결하자. 이는 dijkstra 알고리즘 등을 이용해 어렵지 않게 해낼 수 있다.

아래는 제출한 소스코드이다.

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

int N, M, S, E, R;
vector<pair<int, pair<int, int>>> G[101];
int dist[101][101];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[S][0] = 0;
	pq.push(make_pair(0, make_pair(S, 0)));
	while (!pq.empty()) {
		int cur = pq.top().second.first, t = pq.top().first, c = pq.top().second.second; pq.pop();
		if (dist[cur][c] < t) continue;
		for (auto &p : G[cur]) {
			int nxt = p.first, tt = t + p.second.first, cc = c + p.second.second;
			if (cc <= R && tt < dist[nxt][cc]) dist[nxt][cc] = tt, pq.push(make_pair(tt, make_pair(nxt, cc)));
		}
	}
}

int ans;

void solve() {
	ans = 0x3f3f3f3f;
	for (int n = 0; n < N; n++) G[n].clear();
	while (M--) {
		int x, y, t, c; cin >> x >> y >> t >> c;
		G[x].emplace_back(make_pair(y, make_pair(t, c)));
		G[y].emplace_back(make_pair(x, make_pair(t, c)));
	}
	cin >> S >> E >> R;
	dijkstra();
	for (int c = R; c > -1; c--) {
		ans = min(ans, dist[E][c]);
	}
	if (ans < 0x3f3f3f3f) cout << ans << '\n';
	else cout << '\n';
}

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

	while (cin >> N >> M) solve();
}