Submission #1011285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011285		0pt1mus23	Autobus (COCI22_autobus)	C++14	70 / 70	109 ms	10332 KiB

Main

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()

const int mod = 1e9 +7, sze = 2e5+10, inf = INT_MAX, prime = 1453;

int yol[80][80];
int dp[80][80][80];
void mal(){
    int n,m;
    cin>>n>>m;

    for(int i =0;i<=n;i++){
        for(int j=0;j<=n;j++){
            fill(dp[i][j],dp[i][j]+80,inf);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j){
                yol[i][j]=inf;
                dp[0][i][j]=inf;
            }
            else{
                for(int k=0;k<=n;k++){
                    dp[k][i][j]=0;
                }
            }
        }
        
    }
    for(int i=1;i<=m;i++){
        int u,v,t;
        cin>>u>>v>>t;
        yol[u][v]=min(yol[u][v],t);
    }
    int k,q;
    cin>>k>>q;
    k=min(k,n-1);
    for(int d=0;d<=k;d++){
        for(int x=1;x<=n;x++){
            for(int y=1;y<=n;y++){
                for(int z=1;z<=n;z++){
                    // cout<<d<<" "<<x<<" "<<y<<" "<<dp[d][x][z]<<" "<<yol[z][y]<<endl; 
                    dp[d+1][x][y]=min(dp[d+1][x][y],dp[d][x][z]+yol[z][y]);
                }
            }
        }
    }
    while(q--){
        int u,v;
        cin>>u>>v;
        cout<<(dp[k][u][v]>=inf?-1:dp[k][u][v])<<endl;
    }
} 
 
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    clock_t z = clock();
    int tt = 1;
    // cin>>tt;
    
    while(tt--){
        mal();        
    }
    
    // cerr<<(double)(clock() - z) / CLOCKS_PER_SEC <<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:66:13: warning: unused variable 'z' [-Wunused-variable]
   66 |     clock_t z = clock();
      |             ^

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