제출 #978227

#제출 시각아이디문제언어결과실행 시간메모리
978227Tsagana사이버랜드 (APIO23_cyberland)C++17
8 / 100
246 ms10176 KiB
#include "cyberland.h" // START #include <bits/stdc++.h> #define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie(); #define all(x) x.begin(), x.end() #define vi vector<int> #define pi pair<int, int > #define lb lower_bound #define ub upper_bound #define pb push_back #define eb emplace_back #define mset multiset #define F first #define S second #define pid pair<int, double> #define pdi pair<double, int> using namespace std; vector<pid> adj[100005]; double mindis[100005]; bool reach[100005]; int h, n; void dfs(int u) { reach[u] = 1; if (u == h) return; for (auto [v, w]: adj[u]) { if (!reach[v]) dfs(v); } } void dij(vector<int> &arr) { priority_queue<pdi> pq; for (int i = 0; i < n; i++) { if (reach[i] && mindis[i] < 1e18) pq.push({mindis[i], i}); } vector<bool> vis(n, 0); while(!pq.empty()) { int u = pq.top().S; pq.pop(); if (vis[u]) continue; vis[u] = 1; if (u == h) continue; for (auto [v, w]: adj[u]) { if (reach[v] && !vis[v] && mindis[v] > mindis[u] + w) { mindis[v] = mindis[u] + w; pq.push({mindis[v], v}); } } } vector<pid> tmp; for (int u = 0; u < n; u++) { double mn = mindis[u]; if (reach[u] && arr[u] == 2) { for(auto [v, w]: adj[u]) { if (reach[v] && v != h) mn = min(mn, (mindis[v] + w) / 2.0); } } if(mn < mindis[u]) tmp.pb({u, mn}); } for (auto [u, dis]: tmp) { mindis[u] = min(mindis[u], dis); } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { h = H; n = N; K = min(K, 70); for (int i = 0; i < N; i++) { adj[i].clear(); reach[i] = 0; mindis[i] = 1e18; } for (int i = 0; i < M; i++) { adj[x[i]].pb({y[i], (double)c[i]}); adj[y[i]].pb({x[i], (double)c[i]}); } dfs(0); if (!reach[H]) return -1; mindis[0] = 0; for (int i = 1; i < N; i++) { if (reach[i] && arr[i] == 0) { mindis[i] = 0; } } for (int i = 0; i <= K; i++) dij(arr); return mindis[H]; } //END
#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...