#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 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){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<vector<double>> dp(N, vector<double> (K+2, (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] = 0;
pq.push({0,0,dp[0][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] = 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) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id][u.div2] + v.second < dp[v.first][u.div2]){
dp[v.first][u.div2] = dp[u.id][u.div2] + v.second;
pq.push({v.first, u.div2, dp[v.first][u.div2]});
}
double tmp = (dp[u.id][u.div2] + v.second) / 2.0;
if(u.div2 + 1 <= K && arr[v.first] == 2){
if(tmp < dp[v.first][u.div2+1]){
dp[v.first][u.div2+1] = tmp;
pq.push({v.first, u.div2+1, dp[v.first][u.div2+1]});
}
}
}
}
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_8(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){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<vector<double>> dp(N, vector<double> (K+2, (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] = 0;
pq.push({0,0,dp[0][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] = 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) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id][u.div2] + v.second < dp[v.first][u.div2]){
dp[v.first][u.div2] = dp[u.id][u.div2] + v.second;
pq.push({v.first, u.div2, dp[v.first][u.div2]});
}
double tmp = (dp[u.id][u.div2] + v.second) / 2.0;
if(u.div2 + 1 <= K && arr[v.first] == 2){
if(tmp < dp[v.first][u.div2+1]){
dp[v.first][u.div2+1] = tmp;
pq.push({v.first, u.div2+1, dp[v.first][u.div2+1]});
}
}
}
}
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);
if(K <= 30) return sub_1_4_7(N,M,K,H,x,y,c,arr);
return sub_8(N,M,min(K,100),H,x,y,c,arr);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
368 KB |
Correct. |
2 |
Correct |
22 ms |
472 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
468 KB |
Correct. |
2 |
Correct |
35 ms |
448 KB |
Correct. |
3 |
Correct |
34 ms |
424 KB |
Correct. |
4 |
Correct |
26 ms |
468 KB |
Correct. |
5 |
Correct |
26 ms |
464 KB |
Correct. |
6 |
Correct |
22 ms |
1504 KB |
Correct. |
7 |
Correct |
28 ms |
1476 KB |
Correct. |
8 |
Correct |
13 ms |
2644 KB |
Correct. |
9 |
Correct |
27 ms |
392 KB |
Correct. |
10 |
Correct |
25 ms |
340 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
460 KB |
Correct. |
2 |
Correct |
26 ms |
460 KB |
Correct. |
3 |
Correct |
26 ms |
468 KB |
Correct. |
4 |
Correct |
28 ms |
384 KB |
Correct. |
5 |
Correct |
29 ms |
384 KB |
Correct. |
6 |
Correct |
6 ms |
1364 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
278 ms |
27272 KB |
Correct. |
2 |
Correct |
289 ms |
1128 KB |
Correct. |
3 |
Correct |
243 ms |
1180 KB |
Correct. |
4 |
Correct |
271 ms |
1088 KB |
Correct. |
5 |
Correct |
218 ms |
452 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
504 KB |
Correct. |
2 |
Correct |
26 ms |
480 KB |
Correct. |
3 |
Correct |
25 ms |
472 KB |
Correct. |
4 |
Correct |
24 ms |
1492 KB |
Correct. |
5 |
Correct |
23 ms |
384 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
488 KB |
Correct. |
2 |
Correct |
25 ms |
520 KB |
Correct. |
3 |
Correct |
48 ms |
9012 KB |
Correct. |
4 |
Correct |
16 ms |
1200 KB |
Correct. |
5 |
Correct |
26 ms |
396 KB |
Correct. |
6 |
Correct |
24 ms |
388 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
288 ms |
1540 KB |
Correct. |
2 |
Correct |
42 ms |
2364 KB |
Correct. |
3 |
Correct |
885 ms |
29840 KB |
Correct. |
4 |
Correct |
602 ms |
8016 KB |
Correct. |
5 |
Correct |
1699 ms |
49956 KB |
Correct. |
6 |
Correct |
724 ms |
41236 KB |
Correct. |
7 |
Correct |
537 ms |
8200 KB |
Correct. |
8 |
Correct |
509 ms |
1676 KB |
Correct. |
9 |
Correct |
246 ms |
2120 KB |
Correct. |
10 |
Correct |
248 ms |
1540 KB |
Correct. |
11 |
Correct |
502 ms |
968 KB |
Correct. |
12 |
Correct |
256 ms |
1620 KB |
Correct. |
13 |
Correct |
288 ms |
1684 KB |
Correct. |
14 |
Correct |
504 ms |
10984 KB |
Correct. |
15 |
Correct |
501 ms |
3392 KB |
Correct. |
16 |
Correct |
249 ms |
1712 KB |
Correct. |
17 |
Correct |
325 ms |
1568 KB |
Correct. |
18 |
Correct |
320 ms |
1500 KB |
Correct. |
19 |
Correct |
727 ms |
1632 KB |
Correct. |
20 |
Correct |
19 ms |
744 KB |
Correct. |
21 |
Correct |
20 ms |
1048 KB |
Correct. |
22 |
Correct |
38 ms |
3272 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1418 ms |
7300 KB |
Correct. |
2 |
Correct |
189 ms |
8756 KB |
Correct. |
3 |
Correct |
856 ms |
94284 KB |
Correct. |
4 |
Correct |
1436 ms |
7340 KB |
Correct. |
5 |
Execution timed out |
3061 ms |
168076 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |