Submission #696616

#	Time	Username	Problem	Language	Result	Execution time	Memory
696616		socpite	Autobus (COCI22_autobus)	C++17	70 / 70	126 ms	5116 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;
typedef long double ld;

const int maxn = 75;
const ll inf = 1e18+5;

int n, m, k, q;

ll d[75][75][75];

ll adj[75][75];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j)adj[i][j] = 0;
            else adj[i][j] = inf;
        }
    }
    for(int i = 0; i < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        adj[a][b] = min<ll>(adj[a][b], w);
    }
    cin >> k >> q;
    k = min(k, n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int l = 0; l <= k; l++){
                if(l == 0 && i == j)d[i][j][l] = 0;
                else d[i][j][l] = inf;
            }
        }
    }
    for(int l = 1; l <= k; l++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int v = 1; v <= n; v++){
                    d[i][j][l] = min(d[i][j][l], d[i][v][l-1] + adj[v][j]);
                }
            }
        }
    }
    while(q--){
        int a, b;
        cin >> a >> b;
        if(d[a][b][k] >= inf)cout << "-1";
        else cout << d[a][b][k];
        cout << "\n";
    }
    
}

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