oj.uz

답안 #699576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699576 2023-02-17T12:27:50 Z Gital Autobus (COCI22_autobus) C++11
0 / 70
 3 ms 468 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;

pair<ll,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++) {
        for(int j = 0; j <= n; j++) {
            dp[i][j].first = -1;
            dp[i][j].second = 0;
            checked[j] = false;
        }
        dp[i][i].first = 0; dp[i][i].second = 0;
        while(true) {
            ll minV = LLONG_MAX; ll minIndex = 0;
            for(int j = 1; j <= n; j++) {
                if(dp[i][j].first != -1 && !checked[j] && dp[i][j].first < minV) {
                    minV = dp[i][j].first;
                    minIndex = j;
                }
            }
            if(minIndex == 0) break;
            checked[(int)minIndex] = true;
            if(dp[i][(int)minIndex].second >= k) continue;
            for(int j = 1; j <= n; j++) {
                if(path[minIndex][j] != 0) {
                    if(dp[i][j].first == -1 || dp[i][j].first > path[minIndex][j] + minV) {
                        dp[i][j].first = path[minIndex][j] + minV;
                        dp[i][j].second = dp[i][minIndex].second + 1;
                    }
                }
            }
        }
    }
    for(int i = 0; i < q; i++) {
        cin >> a >> b;
        cout << dp[a][b].first << endl;
    }
    return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 440 KB Output is correct
2 Incorrect 3 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -