This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "cyberland.h"
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int P = 60;
const int N = 1e5 + 10;
const double OO = 1e18;
const double TSH = 1e-9;
int k, n, h;
vector<pii> g[N];
char con[N], bio[N][P], type[N];
double dp[N][P], ans;
set<pair<double, pii>> s;
void check(int u) {
if(con[u]) {
return;
}
con[u] = 1;
if(u == h) {
return;
}
for(pii e : g[u]) {
check(e.X);
}
}
void dijkstra() {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < P; ++j) {
dp[i][j] = OO;
bio[i][j] = 0;
}
}
dp[h][0] = 0;
s.insert({dp[h][0], {h, 0}});
for(; !s.empty(); ) {
int u = s.begin()->Y.X;
int p = s.begin()->Y.Y;
s.erase(s.begin());
if(bio[u][p] || type[u] == 0) {
ans = min(ans, dp[u][p]);
}
bio[u][p] = 1;
for(pii e : g[u]) {
int v = e.X, w = e.Y, pp = type[v] == 2 ? min(p + 1, P - 1) : p;
if(!bio[v][pp] && abs(dp[v][pp] - dp[u][p] - (double) w / (1LL << p)) > TSH) {
dp[v][pp] = dp[u][p] + (double) w / (1LL << p);
s.insert({dp[v][pp], {v, pp}});
}
}
}
}
double solve(int nn, int m, int kk, int hh, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
n = nn;
k = min(kk, P);
h = hh;
for(int i = 0; i < n; ++i) {
con[i] = 0;
g[i].clear();
}
for(int i = 0; i < m; ++i) {
g[x[i]].PB({y[i], c[i]});
g[y[i]].PB({x[i], c[i]});
}
for(int i = 0; i < n; ++i) {
type[i] = arr[i];
}
type[0] = 0;
check(0);
if(!con[h]) {
return -1;
}
ans = OO;
dijkstra();
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |