Submission #569215

#	Time	Username	Problem	Language	Result	Execution time	Memory
569215		knightron0	Autobus (COCI22_autobus)	C++14	70 / 70	140 ms	10060 KiB

Main

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

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 74;

int dp[MAXN][MAXN][MAXN];
int adj[MAXN][MAXN];
vector<pair<int, int>> dest[MAXN];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    int n, m;
    cin>>n>>m;
    clr(adj, -1);
    for(int i= 0;i<m;i++){
        int t1, t2, t3;
        cin>>t1>>t2>>t3;
        if(adj[t1][t2] == -1){
            adj[t1][t2] = t3;
        } else {
            adj[t1][t2] = min(adj[t1][t2], t3);
        }
    }
    for(int i= 1;i<=n;i++){
        for(int j= 1;j<=n;j++){
            if(adj[j][i] != -1){
                dest[i].pb({j, adj[j][i]});
            }
        }
    }
    int q, K;
    cin>>K>>q;
    clr(dp, -1);
    for(int i = 1;i<=n;i++){
        dp[i][i][0] = 0;
        for(int j= 1;j<=n;j++){
            dp[i][j][1] = adj[i][j];
        }
        dp[i][i][1] = 0;
    }
    for(int k = 2;k<=min(n+1, K);k++){
        for(int i = 1;i<=n;i++){
            for(int j= 1;j<=n;j++){
                if(i == j) {
                    dp[i][j][k] = 0;
                    continue;
                }
                dp[i][j][k] = INF;
                for(auto x: dest[j]){
                    if(dp[i][x.fr][k-1] == -1) continue;
                    dp[i][j][k] = min(dp[i][j][k], dp[i][x.fr][k-1]+x.sc);
                }
                if(dp[i][j][k] == INF){
                    dp[i][j][k] = -1;
                }
            }
        }
    }
    while(q--){
        int t1, t2;
        cin>>t1>>t2;
        int ans = INF;
        for(int i= 1;i<=min(n+1, K);i++){
            if(dp[t1][t2][i] == -1) continue;
            ans = min(ans, dp[t1][t2][i]);
        }
        if(ans == INF) ans = -1;
        cout<<ans<<endl;
    }
    return 0;
}


// At most 70*70 bus routes
// q = 70*70
// DP[i][j][k] = min(DP[i][a][x] + DP[b][j][k-x] + T(ab))

// dp[i][j][k] = min(dp[i][a][k-1] + T(aj))

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