#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
using si = set<int>;
using mii = map<int, int>;
#define sz(x) (int)size(x)
#define pb emplace_back
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define fr first
#define sc second
#define fo(i, end) for (int i = 0; i < end; i++)
#define foo(i, start, end) for (int i = start; i < end; i++)
template<typename T> inline void domin(T &x, T y) {if (y < x) x = y;}
template<typename T> inline void domax(T &x, T y) {if (y > x) x = y;}
template<typename T, typename U> ostream& operator<<(ostream &os, const pair<T, U> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template < typename T_container, typename T = typename enable_if < !is_same<T_container, string>::value, typename T_container::value_type >::type > ostream & operator<<(ostream &os, const T_container &a) { os << '{'; string sep; for (const T &x : a) os << sep << x, sep = ", "; return os << '}';}
void debug() {cerr << endl;}
template <typename Head, typename... Tail> void debug(Head h, Tail... t) {cerr << h << ' '; debug(t...);}
#ifdef singlabharat
#define debug(...) cerr << "(" << #__VA_ARGS__ << ") : ", debug(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MX = 2e5 + 2, MOD = 1e9 + 7;
double INF = 1e18;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
domin(K, 70);
vector<vpii> g(N);
fo(i, M) {
g[x[i]].pb(pair(y[i], c[i]));
g[y[i]].pb(pair(x[i], c[i]));
}
using state = tuple<double, int, int>;
vb vis(N);
queue<int> q;
q.push(0);
vis[0] = true;
while (!empty(q)) {
int u = q.front();
q.pop();
if (u == H) continue;
for (auto [v, _] : g[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
if (!vis[H]) return -1;
priority_queue < state, vector<state>, greater<state>> pq;
vector<vector<double>> dist(N, vector<double>(K + 1, INF)); // min dist till u with k divs done
pq.push({0.0, 0, 0});
dist[0][0] = 0.0;
while (!empty(pq)) {
auto [_, divs, u] = pq.top();
pq.pop();
if (u == H) continue;
for (auto [v, w] : g[u]) {
if (arr[u] == 0 and w < dist[v][divs]) {
dist[v][divs] = w;
pq.push({dist[v][divs], divs, v});
} if ((arr[u] == 1 or arr[u] == 2) and dist[u][divs] + w < dist[v][divs]) {
dist[v][divs] = dist[u][divs] + w;
pq.push({dist[v][divs], divs, v});
} if (arr[u] == 2 and divs < K and dist[u][divs] / 2 + w < dist[v][divs + 1]) {
dist[v][divs + 1] = dist[u][divs] / 2 + w;
pq.push({dist[v][divs + 1], divs + 1, v});
}
}
}
return *min_element(begin(dist[H]), end(dist[H]));
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
468 KB |
Correct. |
2 |
Correct |
22 ms |
468 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
688 KB |
Correct. |
2 |
Correct |
32 ms |
700 KB |
Correct. |
3 |
Correct |
30 ms |
684 KB |
Correct. |
4 |
Correct |
31 ms |
696 KB |
Correct. |
5 |
Correct |
31 ms |
680 KB |
Correct. |
6 |
Correct |
27 ms |
3936 KB |
Correct. |
7 |
Correct |
38 ms |
3800 KB |
Correct. |
8 |
Correct |
17 ms |
7508 KB |
Correct. |
9 |
Correct |
31 ms |
428 KB |
Correct. |
10 |
Correct |
30 ms |
340 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
596 KB |
Correct. |
2 |
Correct |
35 ms |
688 KB |
Correct. |
3 |
Correct |
33 ms |
668 KB |
Correct. |
4 |
Correct |
33 ms |
340 KB |
Correct. |
5 |
Correct |
36 ms |
464 KB |
Correct. |
6 |
Correct |
7 ms |
3284 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
322 ms |
21312 KB |
Correct. |
2 |
Correct |
553 ms |
732 KB |
Correct. |
3 |
Correct |
474 ms |
788 KB |
Correct. |
4 |
Correct |
532 ms |
792 KB |
Correct. |
5 |
Correct |
381 ms |
448 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
684 KB |
Correct. |
2 |
Correct |
28 ms |
628 KB |
Correct. |
3 |
Correct |
27 ms |
656 KB |
Correct. |
4 |
Correct |
28 ms |
3704 KB |
Correct. |
5 |
Correct |
24 ms |
420 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
632 KB |
Correct. |
2 |
Correct |
24 ms |
636 KB |
Correct. |
3 |
Correct |
46 ms |
7172 KB |
Correct. |
4 |
Correct |
20 ms |
2568 KB |
Correct. |
5 |
Correct |
28 ms |
424 KB |
Correct. |
6 |
Correct |
30 ms |
680 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
502 ms |
2352 KB |
Correct. |
2 |
Correct |
90 ms |
3620 KB |
Correct. |
3 |
Correct |
1492 ms |
27292 KB |
Correct. |
4 |
Correct |
1191 ms |
6912 KB |
Correct. |
5 |
Correct |
2357 ms |
81268 KB |
Correct. |
6 |
Correct |
1202 ms |
40220 KB |
Correct. |
7 |
Correct |
1156 ms |
7004 KB |
Correct. |
8 |
Correct |
1069 ms |
1544 KB |
Correct. |
9 |
Correct |
428 ms |
1968 KB |
Correct. |
10 |
Correct |
402 ms |
2252 KB |
Correct. |
11 |
Correct |
1037 ms |
1004 KB |
Correct. |
12 |
Correct |
468 ms |
2032 KB |
Correct. |
13 |
Correct |
495 ms |
2136 KB |
Correct. |
14 |
Correct |
1018 ms |
8968 KB |
Correct. |
15 |
Correct |
1284 ms |
2764 KB |
Correct. |
16 |
Correct |
442 ms |
2084 KB |
Correct. |
17 |
Correct |
556 ms |
2144 KB |
Correct. |
18 |
Correct |
476 ms |
1664 KB |
Correct. |
19 |
Correct |
1202 ms |
2388 KB |
Correct. |
20 |
Correct |
26 ms |
512 KB |
Correct. |
21 |
Correct |
32 ms |
1144 KB |
Correct. |
22 |
Correct |
107 ms |
5144 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1639 ms |
7692 KB |
Correct. |
2 |
Correct |
302 ms |
14136 KB |
Correct. |
3 |
Correct |
704 ms |
67668 KB |
Correct. |
4 |
Correct |
2751 ms |
4700 KB |
Correct. |
5 |
Execution timed out |
3039 ms |
289504 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |