| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1194984 | Shadow1 | 사이버랜드 (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include "cyberland_apio23.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << ' ';}cout << '\n';
#define output_pairvector(v) for(auto &x : v){cout << x.first << " " << x.second << '\n';}
#define read_vector(v) for(auto &x : v){cin >> x;}
#define vt vector
#define pb push_back
#define eb emplace_back
#define pii pair<ll, ll>
#define pdd pair<ld, ld>
#define fir first
#define sec second
#define sz(x) ll(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
const ll maxn = 1e5 + 5;
const ll INF = 1e15;
vector<bool> vis(maxn);
vector<pii> adj[maxn];
ll n, m, h, k;
void dfs(int u) {
vis[u] = true;
if(u == h) return;
for(auto &v : adj[u]) {
if(!vis[v.fir]) dfs(v.fir);
}
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
n = N, m = M, h = H, k = K;
k = min(k, 70ll);
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]);
}
dfs(0);
vector<int> s = {0}; // source nodes
for(int i=1; i<n; ++i) {
if(arr[i] == 0 && vis[i])
s.push_back(i);
}
// output_vector(s);
vector<vector<ld>> dist(n, vector<ld>(k+1, INF));
priority_queue<pair<pair<ld, int>, int>, vector<pair<pair<ld, int>, int>>, greater<pair<pair<ld, int>, int>>> pq;
for(auto &S : s){
for(int i=0; i<=k; ++i)
dist[S][i] = 0;
pq.push({{0, S}, 0});
}
while(!pq.empty()) {
ld w = pq.top().fir.fir;
ll u = pq.top().fir.sec, j = pq.top().sec;
pq.pop();
// show(u);
if(w > dist[u][j] || u == h) continue;
for(auto &v : adj[u]) {
if(arr[v.fir] == 0) continue;
if(j < k && arr[v.fir] == 2 && (dist[u][j] + v.sec) / 2.0 < dist[v.fir][j+1]) {
dist[v.fir][j+1] = (dist[u][j] + v.sec) / 2.0;
pq.push({{dist[v.fir][j+1], v.fir}, j+1});
}
if(dist[u][j] + v.sec < dist[v.fir][j]) {
dist[v.fir][j] = dist[u][j] + v.sec;
pq.push({{dist[v.fir][j], v.fir}, j});
}
}
}
ld ans = INF;
for(int i=0; i<=k; ++i)
ans = min(ans, dist[h][i]);
if(!vis[h]) ans = -1;
for(int i=0; i<n; ++i) {
vis[i] = false;
adj[i].clear();
}
return ans;
}