제출 #967098

#제출 시각아이디문제언어결과실행 시간메모리
967098Syrius사이버랜드 (APIO23_cyberland)C++17
44 / 100
33 ms12112 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 < ll , ll > #define vint vector < int > #define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL) const ll inf = 1e18 + 9; const int mxn = 2e5 + 2; const int mod = 1e9 + 7; vector < vector < pint > > adj(mxn); ll dis[mxn]; bool vis[mxn]; void dfs(int x , int par , int H) { if (vis[x]) return; vis[x] = 1; if (x == H) return; for (auto i : adj[x]) { if (i.ff == par) continue; dfs(i.ff , 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(); dis[i] = -2; vis[i] = 0; } for (int i = 0; i < m; i++) { adj[x[i]].push_back({y[i] , c[i]}); adj[y[i]].push_back({x[i] , c[i]}); } dfs(0 , 0 , H); priority_queue < pint > q; q.push({0 , H}); ll ans = inf; while (!q.empty()) { pint p = q.top(); q.pop(); if (dis[p.ss] != -2) continue; dis[p.ss] = -p.ff; if (arr[p.ss] == 0 && vis[p.ss]) ans = min(ans , dis[p.ss]); if (p.ss == 0) { ans = min(ans , dis[0]); continue; } for (pint i : adj[p.ss]) { q.push({p.ff - i.ss , i.ff}); } } if (!vis[H]) 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...