Submission #526006

#	Time	Username	Problem	Language	Result	Execution time	Memory
526006		n00bie_1004	Autobus (COCI22_autobus)	C++17	70 / 70	134 ms	15072 KiB

Main

#include <bits/stdc++.h>
typedef long long int ll; 

const ll inf = 1e18;

using namespace std;

int main(){ 
    ios_base::sync_with_stdio(false); cin.tie(NULL); 
    ll n, m;
    cin >> n >> m;
    vector<array<ll, 3>> edge(m); 
    for(auto &[u, v, w] : edge)
        cin >> u >> v >> w, --u, --v;
    ll val[n][n];
    for(ll i = 0; i < n; i++)
        for(ll j = 0; j < n; j++)
            val[i][j] = inf;  
    for(auto [u, v, w] : edge)
        val[u][v] = min(val[u][v], w);
    ll k, q; 
    cin >> k >> q; 
    if(k > n - 1)
        k = n - 1; 
    ll dp[k + 1][n][n];
    for(ll l = 0; l <= k; l++)
        for(ll i = 0; i < n; i++)
            for(ll j = 0; j < n; j++)
                dp[l][i][j] = inf; 
    for(ll i = 0; i < n; i++)
        dp[0][i][i] = 0; 
    for(ll l = 1; l <= k; l++)
        for(ll v = 0; v < n; v++)
            for(ll i = 0; i < n; i++)
                for(ll j = 0; j < n; j++)
                    if(dp[l - 1][i][v] != inf && edge[v][j] != inf)
                        dp[l][i][j] = min(dp[l][i][j], dp[l - 1][i][v] + val[v][j]); 
    while(q--){
        ll u, v, ans = inf; 
        cin >> u >> v; --u; --v; 
        for(ll l = 0; l <= k; l++)
            ans = min(ans, dp[l][u][v]);
        cout << (ans != inf ? ans : -1) << "\n"; 
    }
}

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