#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const ll INF = 1e9 + 1;
ll dp[71][71];
ll path[71][71];
bool checked[71];
ll n,m,k,q;
ll a,b,t;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> a >> b >> t;
if(path[a][b] == 0 || path[a][b] > t) path[a][b] = t;
}
cin >> k >> q;
for(int i = 1; i <= n; i++) {
pair<ll,ll> dist[71];
for(int j = 0; j <= n; j++) {
dp[i][j] = -1;
dist[j].first = LLONG_MAX;
dist[j].second = LLONG_MAX;
checked[j] = false;
}
dp[i][i] = 0; dist[i].first = 0; dist[i].second = 0;
while(true) {
ll minV = LLONG_MAX; ll minIndex = 0;
for(int j = 1; j <= n; j++) {
if(!checked[j] && dist[j].second < k && dist[j].first < minV) {
minV = dist[j].first;
minIndex = j;
}
}
//cout << minIndex << endl;
if(minIndex == 0) break;
checked[(int)minIndex] = true;
//if(dp[i][(int)minIndex].second >= k) continue;
//cout << dist[(int)minIndex].second << endl;
for(int j = 1; j <= n; j++) {
if(path[minIndex][j] != 0) {
if(dp[i][j] == -1 || dp[i][j] > path[minIndex][j] + minV) {
dp[i][j] = path[minIndex][j] + minV;
}
if(dist[j].second > dist[(int)minIndex].second + 1) {
dist[j].first = path[minIndex][j] + minV;
dist[j].second = dist[(int)minIndex].second + 1;
checked[(int)minIndex] = false;
//cout << dist[(int)minIndex].second << endl;
}
}
}
}
}
for(int i = 0; i < q; i++) {
cin >> a >> b;
cout << dp[a][b] << endl;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |