제출 #967039

#제출 시각아이디문제언어결과실행 시간메모리
967039dubabuba사이버랜드 (APIO23_cyberland)C++17
15 / 100
574 ms33984 KiB
#include <bits/stdc++.h> #include "cyberland.h" using namespace std; typedef double dbl; typedef long long i64; typedef vector<int> vi; typedef pair<int, int> pii; #define ff first #define ss second #define MP make_pair const int mxk = 32; const int mxn = 1e5 + 10; vector<pii> adj[mxn]; dbl dis[mxk][mxn]; bool in[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++) { in[i] = 0; adj[i].clear(); } for(int i = 0; i < M; i++) { adj[x[i]].push_back(MP(y[i], c[i])); adj[y[i]].push_back(MP(x[i], c[i])); } priority_queue<pair<pair<dbl, int>, int>> pq; queue<int> q; in[0] = 1; q.push(0); pq.push(MP(MP(0.0, 0), 0)); while(q.size()) { int u = q.front(); q.pop(); if(arr[u] == 0) pq.push(MP(MP(0.0, 0), u)); for(pii p : adj[u]) { int v = p.ff; if(!in[v]) { in[v] = 1; q.push(v); } } } for(int i = 0; i < mxk; i++) for(int j = 0; j < N; j++) dis[i][j] = -1.0; // cout << "BUBA\n"; while(pq.size()) { dbl d = -pq.top().ff.ff; int k = pq.top().ff.ss; int u = pq.top().ss; pq.pop(); if(dis[k][u] != -1.0) continue; dis[k][u] = d; // cout << u << ' ' << k << ": " << d << endl; if(u == H) continue; for(pii p : adj[u]) { int v = p.ff; dbl c = p.ss; if(v == 0) continue; if(arr[v] == 0) continue; pq.push(MP(MP(-(d + c), k), v)); if(arr[v] == 2 && k + 1 <= K && k + 1 < mxk) pq.push(MP(MP(-(d + c) / 2.0, k + 1), v)); } } dbl ans = 1e18; for(int i = 0; i < mxk && i <= K; i++) if(dis[i][H] > -1.0) ans = min(ans, dis[i][H]); if(ans == 1e18) 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...