Submission #1018590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018590		vjudge1	Autobus (COCI22_autobus)	C++17	70 / 70	145 ms	9808 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int int64_t


int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adj(n, vector<int>(n, INT_MAX));
	while(m --) {
		int a, b, t;
		cin >> a >> b >> t;
		a --; b--;
		adj[a][b] = min(adj[a][b], t);
	}
	vector<vector<vector<int>>> dp(n, vector<vector<int>> (n, vector<int> (n, INT_MAX)));
	for(int i = 0; i < n; i ++) dp[i][i][0] = 0;
	for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) dp[i][j][1] = adj[i][j];
	for(int k = 1; k < n; k ++) {
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < n; j ++) {
				for(int t = 0; t < n; t ++) {
					dp[i][j][k] = min(dp[i][t][k - 1] + dp[t][j][1], dp[i][j][k]);
				}
			}
		}
	}
	int k, q;
	cin >> k >> q;
	while(q--) {
		int c, d;
		cin >> c >> d;
		int ans = INT_MAX;
		c --; d--;
		for(int i = 0; i < min(n, k + 1); i ++) {
			ans = min(ans, dp[c][d][i]);
		}
		if(ans == INT_MAX) ans = -1;
		cout << ans << '\n';
	}
}

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