(BOJ) 12763 지각하면 안 돼

문제: https://www.acmicpc.net/problem/12763

 

문제 풀이:

dfs로 풀었다

dist[n]에 pair로 시간이랑 금액 저장

현재 가는 정점이 원래 저장된 값(다른 루트로 온 결과 값)보다 시간이랑 금액 둘 다 손해면 안 가고

둘 중 하나라도 이득이면 감

만약 제한된 금액이나 시간이 이미 지나게 되면 안감

 

 

소스 코드:

typedef pair<int, pair<int, int>> P;
int n,m, time, money,res;
vector<pair<int, int>> dist;
vector<vector<P>> adj;

void dfs(int cur) {
	if (cur == n) {
		res = min(res, dist[cur].second);
		return;
	}
	for (auto &i : adj[cur]) {
		if (dist[i.first].first <= dist[cur].first + i.second.first&&dist[i.first].second <= dist[cur].second + i.second.second) continue;
		else if (dist[cur].first + i.second.first > time || dist[cur].second + i.second.second > money) continue;
		dist[i.first].first = dist[cur].first + i.second.first;
		dist[i.first].second = dist[cur].second + i.second.second;
		dfs(i.first);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n>>time>>money>>m;

	for (int i = 0; i <= n; i++) {
		dist.push_back({inf,inf});
	}
	adj.resize(n + 1);
	res = inf;
	for (int i = 0; i < m; i++) {
		int q, w, e, r;
		cin >> q >> w >> e >> r;
		adj[q].push_back({ w,{e,r} });
		adj[w].push_back({ q,{e,r } });
	}
	dist[1] = make_pair(0, 0);
	dfs(1);
	if (res > money) cout << "-1\n";
	else cout << res << '\n';
	return 0;
}