제출 #1275369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275369		rafsanamin2020	경주 (Race) (IOI11_race)	C++20	21 / 100	17 ms	1668 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

int MX = 1200;

vector<vector<pair<int, int>>> adj(MX);

vector<bool> visited(MX, false);

pair<bool, int> dfs(int x, int K, int l = 0, int nh = 0)
{
  if (visited[x])
  {
    return {false, nh};
  }

  if (l == K)
  {
    return {true, nh};
  }

  visited[x] = true;

  int poss = false, rnh = 1E9;

  for (pair<int, int> v : adj[x])
  {
    pair<bool, int> ret = dfs(v.first, K, l + v.second, nh + 1);

    // cout << x << " " << y << " " << ret.first << " " << ret.second << "__________" << "\n";
    if (ret.first)
    {
      poss = true;
      rnh = min(ret.second, rnh);
    }
  }

  return {poss, rnh};
}

int best_path(int N, int K, int H[][2], int L[])
{

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

  int ans = -1;

  for (int i = 0; i < N; i++)
  {

    visited = vector<bool>(MX, false);
    pair<bool, int>
        ret = dfs(i, K);

    // cout << i << " " << j << " " << ret.first << " " << ret.second << " \n";

    if (ret.first)
    {
      if (ans == -1)
      {
        ans = ret.second;
      }
      else
      {
        ans = min(ans, ret.second);
      }
    }
  }

  return ans;
}

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