| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 203300 | wendy_virgo | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define taskname "IOI11_race"
#define forinc(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordec(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define foreach(i, x) for (auto &i : x)
#define ms(x, n) memset(x, n, sizeof(x))
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define fi first
#define se second
#define pb push_back
#define pf push_front
template<typename TH>
void _dbg(const char* sdbg, TH h)
{
cerr << sdbg << " = " << h << "\n";
}
template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
while (*sdbg != ',') cerr << *sdbg++;
cerr << " = " << h << ",";
_dbg(sdbg + 1, t...);
}
#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";
const int N=2e5+5,INF=1e9;
int n,k,l[N];
vector<pair<int,int>> g[N];
int nEdge[1002][1002],root;
bool mark[1002];
int64_t dist[1002][1002];
void DFS(int u,int fa,int d,int64_t sumW)
{
mark[u]=true;
nEdge[root][u]=d;
dist[root][u]=sumW;
foreach(p,g[u])
{
if(p.fi!=fa)
{
DFS(p.fi,u,d+1,sumW+l[p.se]);
}
}
}
void Calc(int u)
{
root=u;
forinc(i,0,n-1)
{
mark[i]=false;
}
DFS(u,-1,0,0);
}
int Sub2()
{
forinc(i,0,n-1)
{
Calc(i);
}
int ans=INF;
forinc(u,0,n-1)
{
forinc(v,u,n-1)
{
if(dist[u][v]==k)
{
ans=min(ans,nEdge[u][v]);
}
}
}
return ans;
}
int Solve()
{
return Sub2();
}
int best_path(int N,int K,int* H[],int L[])
{
n=n;
k=k;
forinc(i,0,n-2)
{
g[H[i][0]].pb({H[i][1],i});
g[H[i][1]].pb({H[i][0],i});
}
forinc(i,0,n-2)
{
l[i]=L[i];
}
return Solve();
}
//int main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// #ifndef ONLINE_JUDGE
// freopen(taskname".INP","r",stdin);
// #endif // ONLINE_JUDGE
// cin>>n>>k;
// forinc(i,0,n-2)
// {
// int u,v;
// cin>>u>>v;
// g[u].pb({v,i});
// g[v].pb({u,i});
// }
// forinc(i,0,n-2)
// {
// cin>>l[i];
// }
// cout<<Solve();
// return 0;
//}