제출 #968360

#제출 시각아이디문제언어결과실행 시간메모리
968360Syrius사이버랜드 (APIO23_cyberland)C++17
68 / 100
614 ms252812 KiB
#include <bits/stdc++.h> // #include "cyberland.h" using namespace std; // #define int long long #define ll long long #define ff first #define ss second #define pint pair < double , int > #define vint vector < int > #define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL) const double inf = 1e18 + 9; const int mxn = 2e5 + 2; const int mod = 1e9 + 7; vector < vector < pint > > adj(mxn); vint arr_; double dis[77][mxn]; bool vis[mxn]; priority_queue < pint > q[77]; void dfs(int x , int par , int H) { if (vis[x]) return; vis[x] = 1; if (x == H) return; if (arr_[x] == 0) q[0].push({0 , x}); for (pint i : adj[x]) { if (i.ss == par) continue; dfs(i.ss , x , H); } } double solve(int n , int m , int k , int H , vint x , vint y , vint c , vint arr) { for (int i = 0; i < n; i++) { adj[i].clear(); vis[i] = 0; } k = min(k , 76); for (int i = 0; i <= k; i++) { for (int j = 0; j < n; j++) { dis[i][j] = -1; } } arr_ = arr; for (int i = 0; i < m; i++) { adj[x[i]].push_back({c[i] , y[i]}); adj[y[i]].push_back({c[i] , x[i]}); } dfs(0 , 0 , H); q[0].push({0 , 0}); for (int i = 0; i <= k; i++) { while (!q[i].empty()) { pint p = q[i].top(); q[i].pop(); if (dis[i][p.ss] != -1) continue; dis[i][p.ss] = -p.ff; if (p.ss == H) continue; for (pint j : adj[p.ss]) { if (arr[j.ss] == 0) continue; q[i].push({p.ff - j.ff , j.ss}); if (arr[j.ss] == 2) q[i+1].push({(p.ff - j.ff) / 2 , j.ss}); } } } double ans = inf; for (int i = 0; i <= k; i++) { if (dis[i][H] != -1) ans = min(ans , dis[i][H]); } if (ans == inf) return -1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...