#include <bits/stdc++.h>
using namespace std;
using ll = long long;
double solve(int n, int m, int k, int h, vector<int>x, vector<int>y, vector<int>c, vector<int>arr) {
vector<pair<int, double> >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]});
}
vector<int>bg;
{
int vis[n];
vis[1] = 2;
for (int i = 1; i < n; i++)
vis[i] = 0;
queue<int>q;
q.push(0);
while (!q.empty()) {
int v = q.front();
q.pop();
if (arr[v] == 0 || v == 0) {
bg.push_back(v);
vis[v] = 2;
}
for (size_t i = 0; i < g[v].size(); i++) {
int to = g[v][i].first;
if (to != h && !vis[to]) {
q.push(to);
vis[to] = 1;
}
}
}
vis[h] = 1;
vector<pair<int, double> >g2[n];
for (int v = 0; v < n; v++) {
if (!vis[v])
continue;
for (size_t i = 0; i < g[v].size(); i++) {
int to = g[v][i].first;
if (vis[to] == 1)
g2[v].push_back(g[v][i]);
}
}
for (int i = 0; i < n; i++)
g[i] = g2[i];
}
pair<double, int>d[n];
for (int i = 0; i < n; i++)
d[i] = {1e15, 0};
queue<pair<pair<double, int>, int>>q;
for (size_t i = 0; i < bg.size(); i++)
q.push({{0, k}, bg[i]});
while (!q.empty()) {
pair<double, int>vl = q.front().first;
int v = q.front().second;
q.pop();
if (vl.first < d[v].first || vl.second > d[v].second) {
d[v] = vl;
for (size_t i = 0; i < g[v].size(); i++) {
int to = g[v][i].first;
q.push({{vl.first + g[v][i].second, vl.second}, to});
if (arr[to] == 2 && vl.second)
q.push({{(vl.first + g[v][i].second) / 2, vl.second - 1}, to});
}
}
}
if (d[h].first == 1e15)
return -1;
else
return d[h].first;
}
# | 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... |