#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
double sub_2_5(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<double> dp(N, (double)(1e15));
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]});
}
dp[0] = 0;
pq.push({0,dp[0]});
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id] < u.w) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id] + v.second < dp[v.first]){
dp[v.first] = dp[u.id] + v.second;
pq.push({v.first, dp[v.first]});
}
}
}
if(dp[H] == (double)(1e15)) dp[H] = -1;
return dp[H];
}
double sub_3_6(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<double> dp(N, (double)(1e15));
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]});
}
dp[0] = 0;
pq.push({0,dp[0]});
vector<bool> vis(N,false);
queue<int> Q;
Q.push(0);
vis[0] = true;
while(Q.size()){
int u = Q.front();
Q.pop();
for(pair<int,int> v: G[u]){
if(vis[v.first] == true || v.first == H) continue;
vis[v.first] = true;
Q.push(v.first);
}
}
for(int i=1;i<N;i++){
if(arr[i] == 0 && vis[i] == true){
dp[i] = 0;
pq.push({i,dp[i]});
}
}
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id] < u.w) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id] + v.second < dp[v.first]){
dp[v.first] = dp[u.id] + v.second;
pq.push({v.first, dp[v.first]});
}
}
}
if(dp[H] == (double)(1e15)) dp[H] = -1;
return dp[H];
}
double ssub_1_4_7(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
int div2;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
if(A.w == B.w) return A.div2 > B.div2;
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<vector<double>> dp(N+1, vector<double> (K+2, (double)(1e15)));
vector<vector<int>> vis_go(N+1, vector<int> (K+1, 0));
vector<vector<pair<int,int>>> G(N+1);
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]});
}
dp[0][0] = 0.0;
pq.push({0,0,dp[0][0]});
vector<bool> vis(N+1,false);
queue<int> Q;
Q.push(0);
vis[0] = true;
while(Q.size()){
int u = Q.front();
Q.pop();
for(pair<int,int> v: G[u]){
if(vis[v.first] == true || v.first == H) continue;
vis[v.first] = true;
Q.push(v.first);
}
}
for(int i=1;i<N;i++){
if(arr[i] == 0 && vis[i] == true){
dp[i][0] = 0.0;
pq.push({i,0,dp[i][0]});
}
}
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id][u.div2] < u.w) continue;
if(u.id == H) break;
for(pair<int,int> v: G[u.id]){
double tmp = dp[u.id][u.div2] + (double)(v.second);
if(tmp < dp[v.first][u.div2]){
dp[v.first][u.div2] = tmp;
pq.push({v.first, u.div2, tmp});
}
tmp = tmp / (double)(2);
if(u.div2 + 1 <= K && arr[v.first] == 2 && tmp < dp[v.first][u.div2+1]){
dp[v.first][u.div2+1] = tmp;
pq.push({v.first, u.div2+1, tmp});
}
}
}
double ans = (double)(1e15);
for(int i=0;i<=K;i++) ans = min(ans, dp[H][i]);
if(ans == (double)(1e15)) ans = -1;
return ans;
}
double sub_1_4_7(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
int div2;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
// if(A.w == B.w) return A.div2 > B.div2;
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<vector<double>> dp(N+1, vector<double> (K+2, (double)(1e15)));
vector<vector<int>> vis_go(N+1, vector<int> (K+1, 0));
vector<vector<pair<int,int>>> G(N+1);
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<bool> vis(N+1,false);
function<void(int u)> DFS = [&](int u) -> void{
vis[u] = true;
if(u == H) return;
for(pair<int,int> v: G[u]){
if(vis[v.first] == true) continue;
DFS(v.first);
}
};
DFS(0);
dp[0][0] = 0.0;
pq.push({0,0,dp[0][0]});
vis_go[0][0] = 1;
for(int i=1;i<N;i++){
if(arr[i] == 0 && vis[i] == true){
dp[i][0] = 0.0;
pq.push({i,0,dp[i][0]});
vis_go[i][0] = 1;
}
}
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id][u.div2] < u.w) continue;
for(pair<int,int> v: G[u.id]){
double tmp = dp[u.id][u.div2] + (double)(v.second);
if(tmp < dp[v.first][u.div2] && vis_go[v.first][u.div2] == 0){
dp[v.first][u.div2] = tmp;
vis_go[v.first][u.div2] = 1;
pq.push({v.first, u.div2, tmp});
}
tmp /= 2.0;
if(arr[v.first] == 2 && u.div2 < K && tmp < dp[v.first][u.div2+1] && vis_go[v.first][u.div2+1] == 0){
dp[v.first][u.div2+1] = tmp;
vis_go[v.first][u.div2+1] = 1;
pq.push({v.first, u.div2+1, tmp});
}
}
}
double ans = (double)(1e15);
for(int i=0;i<=K;i++) ans = min(ans, dp[H][i]);
if(ans == (double)(1e15)) ans = -1;
return ans;
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
int check_sub_2_5 = 0;
for(int i=0;i<N;i++) check_sub_2_5 += (arr[i] == 1);
if(check_sub_2_5 == N) return sub_2_5(N,M,K,H,x,y,c,arr);
int check_sub_3_6 = 0;
for(int i=0;i<N;i++) check_sub_3_6 += (arr[i] != 2);
if(check_sub_3_6 == N) return sub_3_6(N,M,K,H,x,y,c,arr);
K = min(K, 100);
if(K <= 100) return sub_1_4_7(N,M,K,H,x,y,c,arr);
return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
468 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
452 KB |
Correct. |
2 |
Correct |
27 ms |
472 KB |
Correct. |
3 |
Correct |
25 ms |
464 KB |
Correct. |
4 |
Correct |
32 ms |
556 KB |
Correct. |
5 |
Correct |
27 ms |
460 KB |
Correct. |
6 |
Correct |
23 ms |
1544 KB |
Correct. |
7 |
Correct |
30 ms |
1480 KB |
Correct. |
8 |
Correct |
12 ms |
2644 KB |
Correct. |
9 |
Correct |
26 ms |
340 KB |
Correct. |
10 |
Correct |
25 ms |
340 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
428 KB |
Correct. |
2 |
Correct |
34 ms |
464 KB |
Correct. |
3 |
Correct |
25 ms |
488 KB |
Correct. |
4 |
Correct |
29 ms |
388 KB |
Correct. |
5 |
Correct |
27 ms |
384 KB |
Correct. |
6 |
Correct |
6 ms |
1364 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
254 ms |
35680 KB |
Correct. |
2 |
Incorrect |
176 ms |
1184 KB |
Wrong Answer. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
496 KB |
Correct. |
2 |
Correct |
26 ms |
416 KB |
Correct. |
3 |
Correct |
24 ms |
468 KB |
Correct. |
4 |
Correct |
24 ms |
1492 KB |
Correct. |
5 |
Correct |
25 ms |
340 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
484 KB |
Correct. |
2 |
Correct |
22 ms |
468 KB |
Correct. |
3 |
Correct |
45 ms |
8948 KB |
Correct. |
4 |
Correct |
15 ms |
1200 KB |
Correct. |
5 |
Correct |
25 ms |
380 KB |
Correct. |
6 |
Correct |
23 ms |
500 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
134 ms |
1092 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
368 ms |
2464 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |