Submission #1199627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199627		edga1	경주 (Race) (IOI11_race)	C++20	9 / 100	366 ms	7752 KiB

race

#include <bits/stdc++.h>

using namespace std;

int best_path(int n, int k, int h[][2], int l[]){
    vector<pair<int,int>> a[n];
    for(int i=0; i<n-1; i++){
        a[h[i][0]].push_back({h[i][1],l[i]});
        a[h[i][1]].push_back({h[i][0],l[i]});
    }
    int m=1e9;
    vector<int> s(n);
    for(int i=0; i<n; i++){
        s[i]=1;
        for(int j=i+1; j<n; j++) s[j]=0;
        queue<pair<int,int>> q,q2;
        q.push({i,0});
        int dist=0;
        while(!q.empty()){
            pair<int,int> pos=q.front();
            q.pop();
            int x=pos.first, v=pos.second;
            s[x]=1;
            if(v==k){
                m=min(m,dist);
                break;
            }
            if(v>k) continue;
            for(int j=0; j<a[x].size(); j++){
                if(!s[a[x][j].first]){
                    q2.push({a[x][j].first,a[x][j].second+v});
                }
            }
            if(q.empty()){
                swap(q,q2);
                dist++;
            }
        }
    }
    if(m==1e9) return -1;
    return m;
}
/*
int main(){
    int n,k;
    cin>>n>>k;
    int h[n-1][2], l[n-1];
    for(int i=0; i<n-1; i++){
        cin>>h[i][0]>>h[i][1]>>l[i];
    }
    cout<<best_path(n,k,h,l);
}
*/

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57