제출 #1199658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199658		aren_dance	Autobus (COCI22_autobus)	C++20	70 / 70	213 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<=n;++i){
        adj[i][i]=0;
    }
    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;
        if(dp[u][v][k]!=1e9){
            cout<<dp[u][v][k]<<'\n';
        }
        else{
            cout<<-1<<'\n';
        }
    }
    return 0;
}

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