제출 #965361

#제출 시각아이디문제언어결과실행 시간메모리
965361dubabuba사이버랜드 (APIO23_cyberland)C++17
0 / 100
27 ms54304 KiB
#include <bits/stdc++.h> #include "cyberland.h" 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 const int mxk = 31; const int mxn = 1e5 + 10; vector<pii> adj[mxn]; dbl dis[mxk][mxn]; bool vis[mxn]; int n, m, k; template<typename T> void ono_min(T &MIN, T CMP) { if(MIN > CMP) MIN = CMP; } double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) { n = N, m = M; for(int i = 0; i < m; i++) { // cout << x[i] << " <-> " << y[i] << endl; 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; for(int i = 0; i < n; i++) for(int j = 0; j <= K; j++) dis[j][i] = -1.0; for(int i = 0; i < n; i++) vis[i] = 0; queue<int> q; vis[0] = 1; q.push(0); pq.push(MP(MP(0.0, 0), 0)); while(q.size()) { int u = q.front(); q.pop(); if(vis[u]) exit(1); cout << "in " << u << ' ' << arr[u] << ' ' << vis[u] << endl; if(arr[u] == 0) pq.push(MP(MP(0.0, 0), u)); for(pii p : adj[u]) { int v = p.ff; // cout << " > " << v << ' ' << arr[v] << ' ' << vis[v] << endl; if(!vis[v]) { vis[v] = 1; q.push(v); } } } 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; for(pii p : adj[u]) { int v = p.ff; dbl c = p.ss; if(dis[k][v] == -1.0) pq.push(MP(MP(-(d + c), k), v)); if(arr[v] == 2 && k < K && k < mxk && dis[k + 1][v] == -1.0) pq.push(MP(MP(-(d + c) / 2.0, k + 1), v)); } } dbl ans = 1e18; for(int i = 0; i <= K; i++) if(dis[i][H] != -1.0) ono_min(ans, dis[i][H]); if(ans < 1e18) return ans; return -1; } /* 2 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 */
#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...