제출 #417716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417716		ioi	경주 (Race) (IOI11_race)	C++14	21 / 100	3064 ms	8188 KiB

race

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

int n , k  , dis[100001] ;
vector<pair<int , int  >> adj[100001];
int vis[100001] , vid ;

int bfs(int s){

    memset(dis , 0 , sizeof dis);

    queue<pair<int , int > > q ;
    q.push({s , 0});
    dis[s] = 0 ; vis[s] = vid ;
    while(!q.empty()){

        auto f = q.front();
        q.pop();
        if(f.second > k)continue ;

        for(auto c : adj[f.first]){

            if(vis[c.first] == vid)continue ;
            int nc = f.second + c.second ;
            if(nc > k)continue ;
            int nd = dis[f.first] + 1 ;
            dis[c.first] = nd ;
            vis[c.first] = vid ;
            q.push({c.first , nc});
            if(nc == k)return nd ;

        }


    }


    return 1e9 ;

}
int best_path(int N, int K, int H[][2], int L[])
{
    k = K ;
    int mn = 1e9 ;


    for(int i = 0 ; i < N ; i ++){
        int from = H[i][0] , to = H[i][1];
        adj[from].push_back({to , L[i]});
        adj[to].push_back({from , L[i]});


    }

    for(int i = 0 ; i < N ; i ++)
        vid ++ , mn = min(mn , bfs(i));



    return (mn == 1e9 ? -1 : mn);
}

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