| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 851245 |
2023-09-19T06:23:00 Z |
dosts |
Autobus (COCI22_autobus) |
C++17 |
|
1 ms |
344 KB |
#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;
vector<vi> got(n+1,vi(n+1,inf));
for (int i=1;i<=m;i++) {
int a,b,c;
cin >> a >> b >> c;
min(got[b][a],c);
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
if (got[i][j] != inf) edges[i].pb({j,got[i][j]});
}
}
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();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
