| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 851240 | dosts | Autobus (COCI22_autobus) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[a].pb({b,c});
}
int k,q;
cin >> k >> q;
k = min(k,70LL);
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[i]) {
fw[i][j][steps] = min(fw[i][j][steps],fw[it.first][j][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]) << endl;
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while (t --> 0) solve();
}