Submission #1272650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272650		witek_cpp	Robot (JOI21_ho_t4)	C++20	100 / 100	123 ms	24136 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, pair<int, ll>>>> g(n + 1);
	f(i, 1, m + 1) {
		int a, b, c;
		ll p;
		cin >> a >> b >> c >> p;
		g[a].pb({b, {c, p}});
		g[b].pb({a, {c, p}});
	}
	const ll INF = 1'420'690'000'000'069;
	vector<ll> sum(m + 1, 0);
	vector<ll> minn(m + 1, INF);
	vector<ll> dist(n + 1, INF);
	priority_queue<pair<ll, int>> kolejka;
	kolejka.push({0, 1});
	while (!kolejka.empty()) {
		ll koszt = -kolejka.top().st;
		int v = kolejka.top().nd;
		kolejka.pop();
		if (dist[v] != INF) continue;
		dist[v] = koszt;
		//cout << "v to " << v << " koszt to " << koszt << "\n";
		if (v == n) {cout << koszt; return 0;}
		for (pair<int, pair<int, ll>> u: g[v]) {
			sum[u.nd.st] += u.nd.nd;
			minn[u.nd.st] = min(minn[u.nd.st], dist[u.st]);
		}
		/*f(i, 1, m + 1) {
			cout << "kolor " << i << " suma " << sum[i] << "   min kol " << maks_kol[i] << "   minn " << minn[i] << "\n";
		}*/
		for (pair<int, pair<int, ll>> u: g[v]) {
			ll kand = u.nd.nd + dist[v];
			kand = min(kand, min(minn[u.nd.st] + sum[u.nd.st] - u.nd.nd, dist[v] + sum[u.nd.st] - u.nd.nd));
			if (dist[u.st] == INF) kolejka.push({-kand, u.st});
		}
		for (pair<int, pair<int, ll>> u: g[v]) {
			sum[u.nd.st] = 0;
			minn[u.nd.st] = INF;
		}
	}
	cout << -1;
	return 0;
}

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42