| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 984825 | Faisal_Saqib | 서열 (APIO23_sequence) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
int n,h;
const int N=1e5+10;
vector<pair<int,long long>> ma[N];
long long arr[N],down[N],dist[N];
long long ans=1e14+10;
void dfs(int x,int p=-1,bool pa=0)
{
if(x==h)
{
dist[x]=0;
return;
}
for(auto [y,w]:ma[x])
{
if(y!=p)
{
dfs(y,x);
dist[x]=min(dist[x],dist[y]+w);
}
}
}
void dp(int x,int p=-1)
{
if(arr[x]==0)
down[x]=0;
if(x==h)
return;
for(auto [y,w]:ma[x])
if(y!=p)
{
dp(y,x);
down[x]=min(down[x],w+down[y]);
}
}
void full_solve(int x,int p=-1,long long up=0)
{
up=min(up,down[x]);
ans=min(ans,up+dist[x]);
if(x==h)
return;
for(auto [y,w]:ma[x])
if(y!=p)
{
full_solve(y,x,up+w);
}
}
double solve(int NP, int m, int k, int HP, vector<int> x, vector<int> y, vector<int> c, vector<int> aas) {
n=NP;
h=HP;
for(int i=0;i<n;i++)
{
ma[i].clear();
dist[i]=down[i]=1e14+10;
arr[i]=aas[i];
}
for(int j=0;j<m;j++)
{
ma[x[j]].push_back({y[j],c[j]});
ma[y[j]].push_back({x[j],c[j]});
}
dfs(0);
down[0]=0;
dp(0);
full_solve(0);
double tap=ans;
return tap;
}