#include "cyberland.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define elif else if
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,m,k,a[N];
double dis[N][35];
vector<pair<int,int>> adj[N];
bool vis[N][35];
void dijkstra(){
priority_queue<pair<double,pair<int,int>>> pq;
pq.push({0,{0,0}});
for (int i=0;i<n;i++) for (int j=0;j<=k;j++) dis[i][j]=-1;
dis[0][0]=0;
while (!pq.empty()){
int x=pq.top().S.F,y=pq.top().S.S;
pq.pop();
if (vis[x][y]) continue;
vis[x][y]=1;
for (auto u:adj[x]){
if (dis[u.F][y]<0 || dis[u.F][y]>dis[x][y]+double(u.S)){
dis[u.F][y]=dis[x][y]+double(u.S);
pq.push({-dis[u.F][y],{u.F,y}});
}
if (!a[u.F]){
dis[u.F][y]=0;
pq.push({0,{u.F,y}});
}
elif (a[u.F]==2 && y+1<=k){
int nd=(dis[x][y]+double(u.S))/2.0;
if (dis[u.F][y+1]<0 || dis[u.F][y+1]>nd){
dis[u.F][y+1]=nd;
pq.push({-nd,{u.F,y+1}});
}
}
}
}return;
}
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) {
n=N;m=M;k=K;
for (int i=0;i<m;i++){
adj[x[i]].pb({y[i],c[i]});
adj[y[i]].pb({x[i],c[i]});
}
for (int i=0;i<n;i++) a[i]=arr[i];
dijkstra();
double ans=dis[H][0];
for (int i=1;i<=k;i++){
if (dis[H][i]<0) continue;
ans=min(ans,dis[H][i]);
}return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
4944 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
5724 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
5720 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
269 ms |
26840 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
5976 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
5980 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
5724 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3032 ms |
13884 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |