#include<bits/stdc++.h>
using namespace std;
int N, M, Q, K;
vector<vector<long long int>> states;
vector<vector<pair<int, int>>> AdjList;
void preprocess(){
bool changed = true;
vector<vector<long long int>> newState(N, vector<long long int>(N));
for(int i = 0; i < K and changed; ++i){
newState = states;
changed = false;
for(int nodeFrom = 0; nodeFrom < N; ++nodeFrom){
for(int nodeTo = 0; nodeTo < N; ++nodeTo){
if(nodeFrom == nodeTo and i > 0) continue;
for(pair<int, int> edge: AdjList[nodeTo]){
long long int dist = (long long)states[nodeFrom][nodeTo] + (long long)edge.second;
int nextNode = edge.first;
//cout << "Iteration: " << i+1 << "\t From: " << nodeFrom << " and " << nodeTo << " to " << nextNode << " distance " << dist << " versus " << states[nodeFrom][nextNode] << endl;
if(states[nodeFrom][nextNode] > dist){
changed = true;
newState[nodeFrom][nextNode] = min(newState[nodeFrom][nextNode], dist);
}
}
}
}
states = newState;
}
}
int main(){
cin >> N >> M;
AdjList = vector<vector<pair<int, int>>>(N);
states = vector<vector<long long int>>(N, vector<long long int>(N, 1e18));
for(int i = 0; i < N; ++i) states[i][i] = 0;
int a, b, w;
for(int i = 0; i < M; ++i){
cin >> a >> b >> w;
a--; b--;
AdjList[a].push_back({b, w});
}
cin >> K >> Q;
preprocess();
while(Q--){
cin >> a >> b;
a--; b--;
if(states[a][b] == 1e18) cout << -1 << endl;
else cout << states[a][b] << endl;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
388 KB |
Output is correct |
2 |
Correct |
10 ms |
416 KB |
Output is correct |
3 |
Correct |
11 ms |
340 KB |
Output is correct |
4 |
Correct |
9 ms |
448 KB |
Output is correct |
5 |
Correct |
10 ms |
340 KB |
Output is correct |
6 |
Correct |
14 ms |
560 KB |
Output is correct |
7 |
Correct |
14 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
10 ms |
424 KB |
Output is correct |
8 |
Correct |
9 ms |
396 KB |
Output is correct |
9 |
Correct |
9 ms |
340 KB |
Output is correct |
10 |
Correct |
9 ms |
448 KB |
Output is correct |
11 |
Correct |
17 ms |
556 KB |
Output is correct |
12 |
Correct |
16 ms |
440 KB |
Output is correct |
13 |
Correct |
423 ms |
11348 KB |
Output is correct |
14 |
Correct |
489 ms |
11232 KB |
Output is correct |
15 |
Correct |
550 ms |
11240 KB |
Output is correct |
16 |
Correct |
543 ms |
11284 KB |
Output is correct |
17 |
Correct |
429 ms |
11368 KB |
Output is correct |
18 |
Correct |
370 ms |
11504 KB |
Output is correct |
19 |
Correct |
421 ms |
11300 KB |
Output is correct |
20 |
Correct |
423 ms |
11408 KB |
Output is correct |
21 |
Correct |
367 ms |
11444 KB |
Output is correct |
22 |
Correct |
430 ms |
11520 KB |
Output is correct |
23 |
Correct |
424 ms |
11560 KB |
Output is correct |
24 |
Correct |
440 ms |
11704 KB |
Output is correct |
25 |
Correct |
420 ms |
11660 KB |
Output is correct |
26 |
Correct |
512 ms |
11596 KB |
Output is correct |
27 |
Correct |
499 ms |
11572 KB |
Output is correct |
28 |
Correct |
516 ms |
11564 KB |
Output is correct |
29 |
Correct |
453 ms |
11084 KB |
Output is correct |
30 |
Correct |
734 ms |
11088 KB |
Output is correct |
31 |
Execution timed out |
1083 ms |
11272 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
9 ms |
388 KB |
Output is correct |
8 |
Correct |
10 ms |
416 KB |
Output is correct |
9 |
Correct |
11 ms |
340 KB |
Output is correct |
10 |
Correct |
9 ms |
448 KB |
Output is correct |
11 |
Correct |
10 ms |
340 KB |
Output is correct |
12 |
Correct |
14 ms |
560 KB |
Output is correct |
13 |
Correct |
14 ms |
468 KB |
Output is correct |
14 |
Correct |
10 ms |
424 KB |
Output is correct |
15 |
Correct |
9 ms |
396 KB |
Output is correct |
16 |
Correct |
9 ms |
340 KB |
Output is correct |
17 |
Correct |
9 ms |
448 KB |
Output is correct |
18 |
Correct |
17 ms |
556 KB |
Output is correct |
19 |
Correct |
16 ms |
440 KB |
Output is correct |
20 |
Correct |
423 ms |
11348 KB |
Output is correct |
21 |
Correct |
489 ms |
11232 KB |
Output is correct |
22 |
Correct |
550 ms |
11240 KB |
Output is correct |
23 |
Correct |
543 ms |
11284 KB |
Output is correct |
24 |
Correct |
429 ms |
11368 KB |
Output is correct |
25 |
Correct |
370 ms |
11504 KB |
Output is correct |
26 |
Correct |
421 ms |
11300 KB |
Output is correct |
27 |
Correct |
423 ms |
11408 KB |
Output is correct |
28 |
Correct |
367 ms |
11444 KB |
Output is correct |
29 |
Correct |
430 ms |
11520 KB |
Output is correct |
30 |
Correct |
424 ms |
11560 KB |
Output is correct |
31 |
Correct |
440 ms |
11704 KB |
Output is correct |
32 |
Correct |
420 ms |
11660 KB |
Output is correct |
33 |
Correct |
512 ms |
11596 KB |
Output is correct |
34 |
Correct |
499 ms |
11572 KB |
Output is correct |
35 |
Correct |
516 ms |
11564 KB |
Output is correct |
36 |
Correct |
453 ms |
11084 KB |
Output is correct |
37 |
Correct |
734 ms |
11088 KB |
Output is correct |
38 |
Execution timed out |
1083 ms |
11272 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |