Submission #526790

#	Time	Username	Problem	Language	Result	Execution time	Memory
526790		Hydroxic_Acid	Autobus (COCI22_autobus)	C++14	70 / 70	202 ms	3776 KiB

Main

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define ll long long

int n, m, q, k;
ll adjm[75][75];
ll memo[75][75][75];

ll dp(ll d, ll x, ll y){
    if(x == y) return 0;
    if(d <= 0) return 1000000000000;
    if(memo[d][x][y] != -1) return memo[d][x][y];
    ll minn = 1000000000000;
    for(int i = 1; i <= n; i++){
        minn = min(minn, dp(d - 1, x, i) + adjm[i][y]);
    }
    return memo[d][x][y] = minn;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(memo, -1, sizeof(memo));
    cin >> n >> m;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            adjm[i][j] = 1000000000000;
            if(i == j) adjm[i][j] = 0;
        }
    }
    for(int i = 0; i < m; i++){
        ll a, b, t; cin >> a >> b >> t;
        adjm[a][b] = min(adjm[a][b], t);
    }
    
    cin >> k >> q;
    k = min(k, n - 1);
    for(int i = 0; i < q; i++){
        ll c, d; cin >> c >> d;
        ll ans = dp(k, c, d);
        if(ans == 1000000000000) ans = -1;
        cout << ans << endl;
    }
    
}

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