# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
982015 | vjudge1 | 앨리스, 밥, 서킷 (APIO23_abc) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
struct Arista
{
int v, p;
};
struct Nodo
{
vector <Arista> ady;
int ability;
};
vector <Nodo> g;
vector <Arista> padre;
vector <bool> vis;
int h;
void clean(int N)
{
g.clear();
padre.clear();
vis.clear();
g.resize(N);
padre.resize(N);
vis.resize(N, false);
}
void dfs(int nodo)
{
if (nodo == h)
{
return;
}
for (auto i : g[nodo].ady)
{
if (!vis[i.v])
{
padre[i.v] = {nodo, i.p};
//cout<<"padre "<<i.v<<": "<<nodo<<" c: "<<i.p<<endl;
vis[i.v] = true;
dfs(i.v);
}
}
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr)
{
h = H;
clean(N);
for (int i = 0; i < M; i++)
{
g[x[i]].ady.push_back({y[i], c[i]});
g[y[i]].ady.push_back({x[i], c[i]});
}
for (int i = 0; i < N; i++)
{
g[i].ability = arr[i];
}
vis[0] = true;
padre[0] = {-1, 0};
dfs(0);
double cost = 0;
int curr = H;
while (curr != -1)
{
cost +=(double) padre[curr].p;
curr =(double) padre[curr].v;
}
return (double)cost;
}