Submission #526723

# Submission time Handle Problem Language Result Execution time Memory
526723 2022-02-16T03:00:49 Z hmm789 Autobus (COCI22_autobus) C++14
15 / 70
9 ms 3044 KB
#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, e, x, y, w, k, q;
	cin >> n >> e;
	int adj[n][n], res;
	int dist[n][n][n];
	memset(adj, -1, sizeof(adj));
	memset(dist, -1, sizeof(dist));
	for(int i = 0; i < e; i++) {
		cin >> x >> y >> w;
		x--; y--;
		if(adj[x][y] == -1) adj[x][y] = w;
		else adj[x][y] = min(adj[x][y], w);
	}
	cin >> k >> q;
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	for(int i = 0; i < n; i++) {
		dist[i][i][0] = 0;
		pq.push(make_pair(0, make_pair(i, 0)));
		while(!pq.empty()) {
			pair<int, pair<int, int>> c = pq.top();
			pq.pop();
			if(c.first != dist[i][c.second.first][c.second.second]) continue;
			if(c.second.second == k || c.second.second == n) continue;
			for(int j = 0; j < n; j++) {
				if(adj[c.second.first][j] == -1) continue;
				if(dist[i][j][c.second.second+1] == -1 || dist[i][j][c.second.second+1] > c.first + adj[c.second.first][j]) {
					dist[i][j][c.second.second+1] = c.first + adj[c.second.first][j];
					pq.push(make_pair(dist[i][j][c.second.second+1], make_pair(j, c.second.second+1)));
				}
			}
		}
	}
	for(int i = 0; i < q; i++) {
		cin >> x >> y;
		x--; y--;
		res = 1e18;
		for(int j = 0; j < n; j++) if(dist[x][y][j] != -1) res = min(res, dist[x][y][j]);
		if(res == 1e18) cout << -1 << '\n';
		else cout << res << '\n';
	}
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 4 ms 3020 KB Output is correct
3 Correct 4 ms 3020 KB Output is correct
4 Correct 4 ms 3020 KB Output is correct
5 Correct 6 ms 3044 KB Output is correct
6 Correct 7 ms 3044 KB Output is correct
7 Correct 9 ms 3020 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -