#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) 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 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);
return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
18 ms |
444 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
488 KB |
Correct. |
2 |
Correct |
37 ms |
448 KB |
Correct. |
3 |
Correct |
28 ms |
468 KB |
Correct. |
4 |
Correct |
26 ms |
468 KB |
Correct. |
5 |
Correct |
27 ms |
468 KB |
Correct. |
6 |
Correct |
22 ms |
1500 KB |
Correct. |
7 |
Correct |
28 ms |
1448 KB |
Correct. |
8 |
Correct |
12 ms |
2644 KB |
Correct. |
9 |
Correct |
24 ms |
340 KB |
Correct. |
10 |
Correct |
27 ms |
340 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
460 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
23 ms |
2132 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
468 KB |
Correct. |
2 |
Correct |
34 ms |
432 KB |
Correct. |
3 |
Correct |
28 ms |
468 KB |
Correct. |
4 |
Correct |
24 ms |
1492 KB |
Correct. |
5 |
Correct |
23 ms |
340 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
468 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
17 ms |
364 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
344 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |