제출 #540596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540596		AlperenT	Autobus (COCI22_autobus)	C++17	70 / 70	170 ms	8308 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 70 + 5, INF = 1e9 + 5;

int n, m, a, b, c, k, q, dist[N][N][N];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            for(int k = 0; k < N; k++){
                dist[i][j][k] = INF;
            }
        }
    }

    cin >> n >> m;

    for(int i = 1; i <= m; i++){
        cin >> a >> b >> c;

        dist[1][a][b] = min(dist[1][a][b], c);
    }

    for(int i = 1; i <= n; i++) dist[1][i][i] = 0;

    for(int i = 2; i <= n; i++){
        for(int a = 1; a <= n; a++){
            for(int b = 1; b <= n; b++){
                dist[i][a][b] = dist[i - 1][a][b];

                for(int v = 1; v <= n; v++){
                    dist[i][a][b] = min(dist[i][a][b], dist[i - 1][a][v] + dist[1][v][b]);
                }
            }
        }
    }

    cin >> k >> q;

    while(q--){
        cin >> a >> b;

        cout << (dist[min(n, k)][a][b] == INF ? -1 : dist[min(n, k)][a][b]) << "\n";
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15