oj.uz

Submission #849501

# Submission time Handle Problem Language Result Execution time Memory
849501 2023-09-14T17:21:29 Z TAhmed33 Ceste (COCI17_ceste) C++
160 / 160
 415 ms 26144 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 608 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 4 ms 860 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2000 KB Output is correct
2 Correct 48 ms 4556 KB Output is correct
3 Correct 61 ms 3820 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 4548 KB Output is correct
2 Correct 415 ms 26144 KB Output is correct
3 Correct 6 ms 860 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1360 KB Output is correct
2 Correct 258 ms 13492 KB Output is correct
3 Correct 12 ms 832 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 1476 KB Output is correct
2 Correct 197 ms 5064 KB Output is correct
3 Correct 180 ms 3780 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 3784 KB Output is correct
2 Correct 161 ms 4312 KB Output is correct
3 Correct 259 ms 5044 KB Output is correct