| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1292304 | phu08 | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pa pair<ll, ll>
using namespace std;
const ll maxN = 2e5 + 6;
const ll maxK = 1e6 + 7;
const ll inf = 1e18;
ll n, k, res;
ll dis1[maxN], dis2[maxN];
vector<pa> adj[maxN];
void BFS(ll s)
{
memset(dis1, 0, sizeof(dis1));
memset(dis2, 0, sizeof(dis2));
queue<ll> q;q.push(s);
while (!q.empty())
{
ll ver = q.front();
q.pop();
for (pa i: adj[ver])
{
if (dis1[i.fi] == 0)
{
dis1[i.fi] = dis1[ver] + i.se;
dis2[i.fi] = dis2[ver] + 1;
if (dis1[i.fi] == k) res = min(res, dis2[i.fi]);
q.push(i.fi);
}
}
}
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> k;
res = inf;
for (ll i = 1; i <= n - 1; i++)
{
ll u, v, c;
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
for (ll i = 0; i <= n; i++) BFS(i);
if (res == inf) cout << "-1";
else cout << res;
}