Submission #851244

#	Time	Username	Problem	Language	Result	Execution time	Memory
851244		dosts	Autobus (COCI22_autobus)	C++17	30 / 70	1053 ms	6224 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
//#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
const int N = 71;
const int inf = 1e9;
vector<pair<int,int>> edges[N];
void solve() {
	int n,m;
	cin >> n >> m;
	for (int i=1;i<=m;i++) {
		int a,b,c;
		cin >> a >> b >> c;
		edges[b].pb({a,c});
	}
	int k,q;
	cin >> k >> q;
	k = min(k,70);
	int fw[n+1][n+1][k+1];
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			for (int kk=0;kk<=k;kk++) {
				fw[i][j][kk] = inf;				
			}
		}
	}
	F(i,n) fw[i][i][0] = 0;
	for (int steps = 1;steps<=k;steps++) {
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=n;j++) {
				for (auto it : edges[j]) {
					fw[i][j][steps] = min(fw[i][j][steps],fw[i][it.first][steps-1]+it.second);
				}
			}
		}
	}
	for (int steps=1;steps<=k;steps++) {
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=n;j++) fw[i][j][steps] = min(fw[i][j][steps],fw[i][j][steps-1]);
		}
	}
	while (q--) {
		int a,b;
		cin >> a >> b;
		cout << (fw[a][b][k]==inf?-1:fw[a][b][k]) << '\n';
	}
}    
 
 
 
 
                                
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}
 
 
 

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