Submission #1087890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087890		whtth	Autobus (COCI22_autobus)	C++14	70 / 70	100 ms	9556 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long n, m, road[71][71], mi[71][71][71], inf=1e12;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("autobus.inp", "r", stdin);
    //freopen("autobus.out", "w", stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)road[i][j]=0;
            else {
                road[i][j]=inf;
            }
            mi[i][j][0]=road[i][j];
        }
    }
    for(int o=1;o<=m;o++){
        long long a, b, v;
        cin>>a>>b>>v;
        road[a][b]=min(road[a][b], v);
        mi[a][b][1]=road[a][b];
    }
    for(int k=1;k<n;k++){///toi da di dc n-1 thanh pho
        for(int i=1;i<=n;i++){///thanh pho di
            for(int j=1;j<=n;j++){///thanh pho den
                mi[i][j][k]=mi[i][j][k-1];
                for(int h=1;h<=n;h++)mi[i][j][k]=min(mi[i][j][k], mi[i][h][k-1]+road[h][j]);///i->j or i->h->j
            }
        }
    }
    long long k, q;
    cin>>k>>q;
    k=min(k, n-1);
    for(int i=1;i<=q;i++){
        long long a, b;
        cin>>a>>b;
        if(mi[a][b][k]<inf)cout<<mi[a][b][k]<<"\n";
        else cout<<"-1\n";
    }
    return 0;
}

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