제출 #968337

#제출 시각아이디문제언어결과실행 시간메모리
968337dubabuba사이버랜드 (APIO23_cyberland)C++17
15 / 100
414 ms35316 KiB
#include <bits/stdc++.h> #include "cyberland.h" #pragma GCC optimize("O3") #pragma GCC target("lzcnt", "popcnt") using namespace std; typedef double dbl; typedef vector<int> vi; typedef long long i64; typedef pair<int, int> pii; #define ff first #define ss second #define MP make_pair template<typename T> void ono_min(T &MIN, T CMP) { if(MIN > CMP) MIN = CMP; } template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; } const int mxk = 32; const int mxn = 1e5 + 10; vector<pii> adj[mxn]; dbl solve(int n, int m, int K, int h, vi x, vi y, vi c, vi arr) { for(int i = 0; i < n; i++) adj[i].clear(); for(int i = 0; i < m; i++) { adj[x[i]].emplace_back(y[i], c[i]); adj[y[i]].emplace_back(x[i], c[i]); } bool in[n]; memset(in, 0, sizeof in); queue<int> q; in[0] = 1; q.push(1); priority_queue<pair<dbl, int>> pq[mxk]; while(q.size()) { int u = q.front(); q.pop(); if(arr[u] == 0) pq[0].push(MP(-0.0, u)); for(pii p : adj[u]) { int v = p.ff; if(!in[v]) { in[v] = 1; q.push(v); } } } pq[0].push(MP(-0.0, 0)); dbl dis[mxk][n], ans = 1e18; for(int k = 0; k <= K && k < mxk; k++) { memset(in, 0, sizeof in); for(int i = 0; i < n; i++) dis[k][i] = 1e18; while(pq[k].size()) { dbl d = -pq[k].top().ff; int u = pq[k].top().ss; pq[k].pop(); if(in[u]) continue; ono_min(dis[k][u], d); in[u] = 1; if(u == h) continue; for(pii p : adj[u]) { int v = p.ff; dbl w = p.ss; if(v == 0 || arr[v] == 0) continue; pq[k].push(MP(-(dis[k][u] + w), v)); if(arr[v] == 2 && k + 1 < mxk) pq[k + 1].push(MP(-(dis[k][u] + w) / 2.0, v)); } } ono_min(ans, dis[k][h]); } return (ans < 1e18) ? ans : -1; } /* 6 3 2 30 2 1 2 1 1 2 12 2 0 4 4 4 30 3 1 0 2 1 0 1 5 0 2 4 1 3 2 2 3 4 3 3 30 2 1 2 1 0 1 1 1 2 1 2 0 1 5 5 30 4 1 2 2 2 1 0 1 1 1 2 1000 2 3 1 3 1 1 2 4 1 5 5 30 4 1 1 2 1 1 0 1 4 1 2 2 2 3 1 3 1 1 2 4 1 4 4 30 3 1 2 1 1 0 1 110 0 2 50 2 3 10 1 3 1 */
#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...