#include "cyberland.h"
#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 1e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 1e13;
const int BASE = 137;
struct toEdge {
int v;
ll w;
};
int n, m, K, H;
int a[N];
vector<toEdge> ke[N];
ll dp[2][N];
bool canGo[N];
void BFS () {
queue<int> Q;
Q.push(1);
canGo[1] = 1;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
iter (&id, ke[u]) {
if (canGo[id.v] == 0) {
canGo[id.v] = 1;
if (id.v != H)
Q.push(id.v);
}
}
}
}
double algo () {
BFS();
if (canGo[H] == 0) {
return -1;
}
struct Data {
ll u, val;
};
struct cmp {
bool operator () (Data A, Data B) { return A.val > B.val; }
};
memset (dp, 0x3f, sizeof dp);
auto Dijkstra = [] (ll dp[], int typ) {
priority_queue<Data, vector<Data>, cmp> pq;
if (typ == 0) {
rep (i, 1, n) dp[i] = INF;
rep (i, 1, n) if ((i == 1) || (a[i] == 0 && canGo[i])) {
dp[i] = 0;
pq.push({i, 0});
}
}
else {
pq.push({H, 0});
dp[H] = 0;
}
while (!pq.empty()) {
int u = pq.top().u;
pq.pop();
iter (&id, ke[u]) {
int v = id.v;
ll w = id.w;
if (dp[v] > dp[u] + w) {
dp[v] = dp[u] + w;
pq.push({v, dp[v]});
}
}
}
};
Dijkstra (dp[0], 0);
Dijkstra (dp[1], 1);
double res = INF;
rep (i ,1, n) {
ll mn = INF;
iter (&id, ke[i]) {
if (id.v != H && a[id.v] == 2) {
mn = min(mn, id.w);
}
}
if (mn == INF) {
res = min(res, (double)(dp[0][i] + dp[1][i]));
continue;
}
double delta = dp[0][i];
if (a[i] == 2) delta /= 2;
rep (k, 1 + (a[i] == 2), K) {
delta += mn;
delta /= 2;
}
// cout << i <<"\n";
res = min(res, delta + dp[1][i]);
}
return res;
}
double solve (int _n, int _m, int _K, int _H, vector<int> _U, vector<int> _V, vector<int> _W, vector<int> _A) {
//void solution() {
// cin >> n >> m >> K >> H;
// ++H;
// rep (i, 1, n) cin >> a[i];
// rep (i, 1, m) {
// int u, v, w;
// cin >> u >> v>> w;
// ++u, ++v;
// ke[u].push_back({v, w});
// ke[v].push_back({u, w});
// }
// cout << algo () <<"\n";
n = _n;
m = _m;
K = _K;
H = _H;
++H;
rep (i, 1, n) {
a[i] = _A[i - 1];
}
rep (i, 0, m - 1) {
int u = _U[i], v = _V[i], w = _W[i];
++u, ++v;
ke[u].push_back({v, w});
ke[v].push_back({u, w});
}
return algo();
}
//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//// file ("c");
// int num_Test = 1;
// cin >> num_Test;
// while (num_Test--)
// solution();
//}
/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4
3 2
0 1 5
0 2 5
1
1 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1397 ms |
5384 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
6716 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
7248 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
9308 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
6996 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
106 ms |
7188 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
6996 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3030 ms |
4944 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
