| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1187621 | Thanhs | Cyberland (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define name "TENBAI"
#define fi first
#define se second
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const double inf = 1 / .0;
double solve(int N, int M, int K, int H, const vector<int>& x, const vector<int>& y, const vector<int>& c, const vector<int>& a)
{
vector<vector<double>> dist(N, vector<double>(K + 1, inf));
vector<vector<pair<int, int>>> g(N);
for (int i = 0; i < M; i++)
g[x[i]].push_back({y[i], c[i]}), g[y[i]].push_back({x[i], c[i]});
priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<>> pq;
for (int i = 0; i < N; i++)
if (!a[i] || i == 1)
{
dist[i][0] = 0;
pq.push({0, i, 0});
}
while (pq.size())
{
auto u = get<1>(pq.top()), t = get<2>(pq.top());
double d = get<0>(pq.top());
pq.pop();
if (dist[u][t] != d)
continue;
for (pair<int, int> v : g[u])
{
if (dist[v.fi][t] > d + v.se)
{
dist[v.fi][t] = d + v.se;
pq.push({dist[v.fi][t], v.fi, t});
}
if (a[v.fi] == 2 && t + 1 <= K && dist[v.fi][t + 1] > (d + v.se) / 2.0)
{
dist[v.fi][t + 1] = (d + v.se) / 2.0;
pq.push({dist[v.fi][t + 1], v.fi, t + 1});
}
}
}
double res = inf;
for (int i = 0; i <= K; i++)
setmin(res, dist[H][i]);
if (res == inf)
res = -1;
return res;
}
// int main()
// {
// cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << endl;
// }