#include <bits/stdc++.h>
using namespace std;
#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const lg N = 71;
lg d[N][N][N], cost[N][N], in_queue[N][N][N];
int main()
{
fastio;
lg n, m;
cin >> n >> m;
memset(d, 0x3f, sizeof(d));
memset(cost, 0x3f, sizeof(cost));
for(int i = 0; i < m; i++)
{
lg a, b, t;
cin >> a >> b >> t;
cost[a][b] = min(cost[a][b], t);
}
priority_queue<array<lg, 3>> pq;
for(int i = 1; i <= n; i++)
{
pq.push({0, i, 0});
in_queue[i][i][0] = true;
d[i][i][0] = 0;
while(pq.size())
{
lg u = pq.top()[1], v = pq.top()[2];
pq.pop();
in_queue[i][u][v] = false;
for(int j = 1; j <= n; j++)
{
if(cost[u][j] > 1e6) continue;
if(d[i][j][v+1] > d[i][u][v]+cost[u][j])
{
d[i][j][v+1] = d[i][u][v]+cost[u][j];
if(in_queue[i][j][v+1]) continue;
in_queue[i][j][v+1] = true;
pq.push({-d[i][j][v+1], j, v+1});
}
}
}
for(int j = 1; j <= n; j++)
{
for(int k = 1; k <= n; k++)
{
d[i][j][k] = min(d[i][j][k], d[i][j][k-1]);
}
}
}
lg k, q;
cin >> k >> q;
k = min(k, n);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
cout << d[i][j][k] << ' ';
}
cout << '\n';
}
while(q--)
{
lg c, e;
cin >> c >> e;
if(d[c][e][k] > 1e9)
{
cout << "-1\n";
continue;
}
cout << d[c][e][k] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
5728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
291 ms |
12116 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
5728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
5728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
