Submission #696629

#	Time	Username	Problem	Language	Result	Execution time	Memory
696629		TranGiaHuy1508	Autobus (COCI22_autobus)	C++17	70 / 70	151 ms	596 KiB

Main

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

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long
const int inf = 1e18;

struct Matrix{
	vector<vector<int>> v;
	int r, c;

	Matrix() = default;
	Matrix(int R): Matrix(R, R) {
		for (int i = 0; i < R; i++) v[i][i] = 0;
	}
	Matrix(int R, int C): r(R), c(C) {
		v.assign(R, vector<int>(C, inf));
	}

	Matrix operator * (const Matrix &M){
		Matrix res(r, M.c);
		for (int i = 0; i < r; i++){
			for (int k = 0; k < c; k++){
				for (int j = 0; j < M.c; j++){
					res.v[i][j] = min(res.v[i][j], v[i][k] + M.v[k][j]);
				}
			}
		}
		return res;
	}

	Matrix operator ^ (int a){
		Matrix res(r);
		for (Matrix exp = *this; a; a >>= 1, exp = exp * exp){
			if (a & 1) res = res * exp;
		}
		return res;
	}
};

void main_program(){
	int n, m; cin >> n >> m;
	
	Matrix mult(n);

	for (int i = 0; i < m; i++){
		int a, b, w; cin >> a >> b >> w;
		a--; b--;
		mult.v[a][b] = min(mult.v[a][b], w);
	}

	int k, q; cin >> k >> q;
	mult = mult ^ k;

	for (int qr = 0; qr < q; qr++){
		int c, d; cin >> c >> d;
		c--; d--;
		Matrix base(1, n); base.v[0][c] = 0;
		Matrix res = base * mult;

		if (res.v[0][d] == inf) cout << "-1\n";
		else cout << res.v[0][d] << "\n";
	}
}

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