Submission #1062416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062416		TAhmed33	Treatment Project (JOI20_treatment)	C++98	35 / 100	266 ms	102864 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e16;
array <ll, 4> a[5001];
int n, m;
vector <int> adj[5001];
ll dist[5001];
void solve () {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> a[i][j];
		}
		a[i][1]--;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][0] <= a[j][0]) {
				if (a[j][1] <= a[i][2] - (a[j][0] - a[i][0])) {
					adj[i].push_back(j);
				}
 			}
			if (a[i][0] >= a[j][0]) {
				if (a[i][2] >= a[j][1] + (a[i][0] - a[j][0])) {
					adj[i].push_back(j);
				}
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		dist[i] = inf;
	}
	priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <>> pq;
	for (int i = 1; i <= m; i++) {
		if (a[i][1] == 0) {
			pq.push({0, i});
			dist[i] = 0;
		}
	}
	while (!pq.empty()) {
		auto k = pq.top();
		pq.pop();
		if (k.first > dist[k.second]) {
			continue;
		}
		for (auto j : adj[k.second]) {
			if (dist[j] > k.first + a[k.second][3]) {
				dist[j] = k.first + a[k.second][3];
				pq.push({dist[j], j});
			}
		}
	}
	ll mn = inf;
	for (int i = 1; i <= m; i++) {
		if (a[i][2] == n) {
			mn = min(mn, dist[i] + a[i][3]);	
		}
	}
	if (mn == inf) {
		cout << -1 << '\n';
	} else {
		cout << mn << '\n';
	}
}		
signed main () {

	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61