#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long double inf=1e15;
struct edge{
int to,s;
long double cost;
inline friend bool operator < (edge fr,edge sc){
return fr.cost>sc.cost;
}
};
int n,m,k;
vector<edge> v[MAXN][31];
long double dist[MAXN][31];
long double ans;
bool vis[MAXN][31];
int ability[MAXN];
priority_queue<edge> q;
bool li[MAXN];
bool dfs(int x,int y){
if(x==y)return true;
li[x]=true;
for(edge e:v[x][0]){
if(li[e.to])continue;
if(dfs(e.to,y))return true;
}
return false;
}
long double gg(long double d,int a,int b){
if(a>b)return d/2;
return d;
}
void dijkstra(){
while(!q.empty()){
edge curr=q.top();
q.pop();
if(vis[curr.to][curr.s])continue;
vis[curr.s][curr.to]=true;
for(edge e:v[curr.to][curr.s]){
if(vis[e.to][e.s] or dist[e.to][e.s]<=gg(dist[curr.to][curr.s],curr.s,e.s)+e.cost)continue;
dist[e.to][e.s]=gg(dist[curr.to][curr.s],curr.s,e.s)+e.cost;
q.push({e.to,e.s,dist[e.to][e.s]});
}
}
}
double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> arr){
n=N; m=M; k=K; H++;
for(int i=1;i<=m;i++){
X[i-1]++; Y[i-1]++;
for(int f=0;f<=k;f++){
if(X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f,C[i-1]});
if(Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f,C[i-1]});
if(f>0 and arr[X[i-1]-1]==2 and X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f-1,C[i-1]});
if(f>0 and arr[Y[i-1]-1]==2 and Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f-1,C[i-1]});
}
}
if(!dfs(1,H))return -1;
for(int i=1;i<=n;i++){
for(int f=0;f<=k;f++){
dist[i][f]=inf;
}
}
for(int i=1;i<=n;i++){
ability[i]=arr[i-1];
if(ability[i]==0 or i==1){
dist[i][k]=0;
q.push({i,k,0});
}
}
dijkstra();
ans=dist[H][k];
for(int i=0;i<=k;i++){
ans=min(ans,dist[H][i]);
}
return ans;
}
/*int main(){
//cout<<solve(3,2,1,2,{0,1},{1,2},{5,4},{1,2,1})<<"\n";
//cout<<solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1})<<"\n";
//cout<<solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1})<<"\n";
return 0;
}*/
Compilation message
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:69:66: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
69 | if(X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f,C[i-1]});
| ^
cyberland.cpp:70:66: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
70 | if(Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f,C[i-1]});
| ^
cyberland.cpp:72:97: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
72 | if(f>0 and arr[X[i-1]-1]==2 and X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f-1,C[i-1]});
| ^
cyberland.cpp:73:97: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
73 | if(f>0 and arr[Y[i-1]-1]==2 and Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f-1,C[i-1]});
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
90408 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
193848 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
213584 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1897 ms |
298724 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
200528 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
213956 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
250696 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2524 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
