Submission #849501

#	Time	Username	Problem	Language	Result	Execution time	Memory
849501		TAhmed33	Ceste (COCI17_ceste)	C++98	160 / 160	415 ms	26144 KiB

ceste

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e3 + 25;
vector <array <int, 3>> adj[MAXN];
int n, m;
long long c[MAXN], t[MAXN];
priority_queue <array <int, 3>, vector <array <int, 3>>, greater <array <int, 3>>> pq;
signed main () {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		adj[a].push_back({b, c, d});
		adj[b].push_back({a, c, d});
	}
	for (int i = 2; i <= n; i++) {
		c[i] = t[i] = 1e16;
	}
	pq.push({0, 0, 1});
	while (!pq.empty()) {
		auto k = pq.top();
		pq.pop();
		c[k[2]] = min(c[k[2]], (int)k[0] * k[1]);
		if (t[k[2]] < k[1]) continue;
		t[k[2]] = k[1];
		for (auto j : adj[k[2]]) {
			if (j[1] + k[1] > 4e6) continue;
			pq.push({k[0] + j[2], k[1] + j[1], j[0]});
		}
	}
	for (int i = 2; i <= n; i++) {
		if (c[i] >= 1e16) cout << -1 << '\n';
		else cout << c[i] << '\n';
	}
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16