Submission #864475

#	Time	Username	Problem	Language	Result	Execution time	Memory
864475		TAhmed33	Autobus (COCI22_autobus)	C++98	70 / 70	263 ms	8264 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e14;
int n;
vector <vector <int>> iden;
vector <vector <int>> mul (vector <vector <int>> a, vector <vector <int>> b) {
	vector <vector <int>> ret (n + 1, vector <int> (n + 1));
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) ret[i][j] = inf;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				ret[i][j] = min(ret[i][j], a[i][k] + b[k][j]);
			}
		}
	}
	return ret;
}
vector <vector <int>> power (vector <vector <int>> a, int b) {
	if (b == 1) return a;
	auto u = power(a, b >> 1);
	u = mul(u, u);
	if (b & 1) u = mul(u, a);
	return u;
}
signed main () {
	cin >> n; int m;
	cin >> m;
	vector <vector <int>> adj(n + 1, vector <int>(n + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j) {
				adj[i][j] = inf;
			}
		}
	}
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a][b] = min(adj[a][b], c);
	}
	iden = vector <vector <int>> (n + 1, vector <int> (n + 1));
	for (int i = 1; i <= n; i++) iden[i][i] = 1;
	int k, q;
	cin >> k >> q;
	adj = power(adj, k);
	while (q--) {
		int a, b;
		cin >> a >> b;
		cout << (adj[a][b] >= inf ? -1 : adj[a][b]) << '\n';	
	}
}

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