제출 #526717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526717		beepbeepsheep	Autobus (COCI22_autobus)	C++17	30 / 70	117 ms	3256 KiB

Main

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

#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
const ll inf=1e15;
const ll mod=1e9+7;
const ll maxn=71;

ll adj[maxn][maxn];
ll dis[maxn][maxn][maxn];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i=0;i<maxn;i++){
        for (int j=0;j<maxn;j++){
            adj[i][j]=inf;
        }
        adj[i][i]=0;
    }
    ll n,e,a,b,w;
    cin>>n>>e;
    for (int i=0;i<e;i++){
        cin>>a>>b>>w;
        adj[a][b]=min(adj[a][b],w);
    }
    ll k,y,u,x;
    cin>>k>>y;
    queue<ii> q;
    memset(dis,-1,sizeof(dis));
    for (int a=1;a<=n;a++){
        q.emplace(a,0);
        dis[a][a][0]=0;
        while (q.size()){
            u=q.front().first;
            x=q.front().second;
            q.pop();
            if (x>k) continue;
            for (int i=1;i<=n;i++){
                if (dis[a][i][x+1]!=-1){
                    dis[a][i][x+1]=min(dis[a][i][x+1],dis[a][u][x]+adj[u][i]);
                } else{
                    dis[a][i][x+1]=dis[a][u][x]+adj[u][i];
                    q.emplace(i,x+1);
                } //n
            }
        }//n2
    }
    for (int i=0;i<y;i++){
        ll ans=inf;
        cin>>a>>b;
        for (int i=0;i<=k;i++){
            if (dis[a][b][i]!=-1) ans=min(ans,dis[a][b][i]);
        }
        cout<<(ans==inf?-1:ans)<<endl;
    }//n2
    return 0;
}

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