Submission #1199643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199643		aren_dance	Autobus (COCI22_autobus)	C++20	0 / 70	5 ms	1860 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N=71;
int dp[N][N][N];
int adj[N][N];
int main()
{
    int n,m,k,q;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            adj[i][j]=1e9;
        }
    }
    for(int i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u][v]=min(w,adj[u][v]);
    }
    cin>>k>>q;
    k=min(k,n);
    for(int i=0;i<=k;++i){
        for(int u=1;u<=n;++u){
            for(int v=1;v<=n;++v){
                dp[u][v][i]=1e9;
            }
        }
    }
    for(int u=1;u<=n;++u){
        dp[u][u][0]=0;
    }
    for(int i=1;i<=k;++i){
        for(int u=1;u<=n;++u){
            for(int v=1;v<=n;++v){
                for(int l=1;l<=n;++l){
                    dp[u][v][i]=min(dp[u][v][i],dp[u][l][i-1]+adj[l][v]);
                }
            }
        }
    }
    while(q--){
        int u,v;
        cin>>u>>v;
        cout<<dp[u][v]<<'\n';
    }
    return 0;
}

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