제출 #306967

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

race

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


vector< pair<int,int> > v[1005];
int used[1005],now;
int ans[1005][1005];
int len[1005][1005];

// find length ans time treveled  from now to vi

void fun(int vi,int cnt,int num){
    //cout<<now<<" "<<vi<<" "<<cnt<<" "<<num<<'\n';

    ans[now][vi]=cnt;
    len[now][vi]=num;

    num++;
    for(int i=0;i<v[vi].size();i++){
        if(used[v[vi][i].first]) continue;
        //cout<<vi<<" "<<v[vi][i].first<<" \n";
        used[v[vi][i].first]=1;
        fun(v[vi][i].first,v[vi][i].second+cnt,num);
    }
}


int best_path(int n, int k, int h[][2], int l[])
{
    // converting array into paired vector
    // v[a]={b,t}
    // there are road from city a to b length of t
    for(int i=0;i<n-1;i++){
        v[h[i][0]].push_back({h[i][1],l[i]});
        v[h[i][1]].push_back({h[i][0],l[i]});
    }
    // finding lenghtes from 1d
    for(int i=0;i<n;i++){
        now=i;
        used[i]=1;
        fun(i,0,0);
        memset(used,0,sizeof(used));
    }

    int mn=INT_MAX;
    /*
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
                cout<<ans[i][j]<<" ";
            } cout<<"\n";
        }
    cout<<"\n";

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
                cout<<len[i][j]<<" ";
        } cout<<"\n";
    }
    
    */
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(ans[i][j]==k){
                mn=min(mn,len[i][j]);
            }
        }
    }
    mn=(mn==INT_MAX ? -1:mn);
  return mn;
}

/*

4 3
0 1 1
1 2 2
1 3 4
2

*/

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void fun(int, int, int)':
race.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<v[vi].size();i++){
      |                 ~^~~~~~~~~~~~~

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