Submission #526685

#	Time	Username	Problem	Language	Result	Execution time	Memory
526685		hmm789	Autobus (COCI22_autobus)	C++14	0 / 70	2 ms	376 KiB

Main

#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], dist[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;
		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]) continue;
			if(c.second.second == k) continue;
			for(int j = 0; j < n; j++) {
				if(adj[c.second.first][j] == -1) continue;
				if(dist[i][j] == -1 || dist[i][j] > c.first + adj[c.second.first][j]) {
					dist[i][j] = c.first + adj[c.second.first][j];
					pq.push(make_pair(dist[i][j], make_pair(j, c.second.second+1)));
				}
			}
		}
	}
	for(int i = 0; i < q; i++) {
		cin >> x >> y;
		x--; y--;
		cout << dist[x][y] << '\n';
	}
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15