# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
880324 | Mardonbekhazratov | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "cyberland.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define int long long
const int INF=1e18;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<pair<int,int>>>v(N);
for(int i=0;i<N-1;i++){
v[x[i]].push_back({y[i],c[i]});
v[y[i]].push_back({x[i],c[i]});
}
vector<bool>vis(N,0);
priority_queue<pair<int,int>>q;
vector<int>dp(N,INF);
dp[0]=0;
q.push({0,0});
while(!q.empty()){
int x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=true;
for(auto [z,y]:v[x]){
if(dp[x]+y<dp[z]){
dp[z]=dp[x]+y;
q.push({-dp[z],z});
}
}
}
if(dp[H]==INF) return -1;
return 1.0*dp[H];
}