Submission #740383

#	Time	Username	Problem	Language	Result	Execution time	Memory
740383		pera	Autobus (COCI22_autobus)	C++14	70 / 70	184 ms	9700 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

#define int ll

const ll mod = 1e9 + 7;


main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n , m , k , q;cin >> n >> m;
	vector<vector<vector<int>>> dp(n + 1 , vector<vector<int>>(n + 1 , vector<int>(n + 1)));
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= n;j ++){
			for(int K = 1;K <= n;K ++){
				dp[i][j][K] = 1e9;
				if(i == j) dp[i][j][K] = 0;
			}
		}
	}
	for(int i = 1;i <= m;i ++){
		int u , v , t;cin >> u >> v >> t;
		dp[u][v][1] = min(dp[u][v][1] , t);
	}
	cin >> k >> q;
	k = min(k , n);
	for(int kk = 2;kk <= k;kk ++){
		for(int j = 1;j <= n;j ++){
			for(int b = 1;b <= n;b ++){
				for(int a = 1;a <= n;a ++){
					dp[j][a][kk] = min(dp[j][a][kk] , dp[j][b][kk - 1] + dp[b][a][1]);
				}
			}
		}
	}
	while(q --){
		int u , v;cin >> u >> v;
		cout << (dp[u][v][k] >= 1e9 ? -1 : dp[u][v][k]) << endl; 
	}
}

Compilation message (stderr)

Main.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main(){
      | ^~~~

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