Submission #526777

#	Time	Username	Problem	Language	Result	Execution time	Memory
526777		hmm789	Autobus (COCI22_autobus)	C++14	70 / 70	371 ms	3524 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], 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;
  	k = min(k, n-1);
	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';
	}
}

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