#include <bits/stdc++.h>
using namespace std;
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){
vector<pair<int,long double> > adj[N];
int n=N,m=M,k=K,h=H;
int sz=100;
k=min(k,sz-1);
for(int i=0; i<m; i++){
adj[x[i]].push_back({y[i],c[i]});
adj[y[i]].push_back({x[i],c[i]});
}
int can[n];
memset(can,0,sizeof(can));
queue<int> q;
q.push(0);
while(!q.empty()){
int a=q.front();
q.pop();
if(can[a]) continue;
can[a]=1;
for(auto i:adj[a]){
if(!can[i.first]&&i.first!=h) q.push(i.first);
if(i.first==h) can[h]=1;
}
}
if(!can[h]) return -1;
long double dist[k+5][n];
for(int j=0; j<k+5; j++) for(int i=0; i<n; i++) dist[j][i]=1e16;
priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,int> > > pq[k+5];
pq[0].push({0,0});
for(int i=1; i<n; i++){
if(arr[i]==0&&can[i]){
pq[0].push({0,i});
}
}
for(int i=0; i<=k; i++){
if(i){
for(int j=0; j<n; j++) dist[i][j]=min(dist[i][j],dist[i-1][j]);
for(int j=0; j<n; j++) if(can[j]) pq[i].push({dist[i][j],j});
}
while(!pq[i].empty()){
long double a=pq[i].top().first;
int b=pq[i].top().second;
pq[i].pop();
if(dist[i][b]<a) continue;
dist[i][b]=a;
if(b==h) continue;
long double cc=a/(long double)2.0;
for(auto j:adj[b]){
if(dist[i][j.first]>a+j.second){
pq[i].push({a+j.second,j.first});
}
if(i<k&&arr[b]==2){
if(dist[i+1][j.first]>cc+j.second){
dist[i+1][j.first]=cc+j.second;
}
}
}
}
}
return (double)dist[k][h];
}/*
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout << solve(3,3,1,2,{0,0,1},{1,2,2},{10000,500000,1},{1,2,1});
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
460 KB |
Correct. |
2 |
Correct |
54 ms |
384 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
245 ms |
2032 KB |
Correct. |
2 |
Correct |
299 ms |
2032 KB |
Correct. |
3 |
Correct |
280 ms |
2092 KB |
Correct. |
4 |
Correct |
295 ms |
2012 KB |
Correct. |
5 |
Correct |
298 ms |
1984 KB |
Correct. |
6 |
Correct |
351 ms |
16860 KB |
Correct. |
7 |
Correct |
455 ms |
16456 KB |
Correct. |
8 |
Correct |
198 ms |
33200 KB |
Correct. |
9 |
Correct |
185 ms |
640 KB |
Correct. |
10 |
Correct |
176 ms |
532 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
301 ms |
2128 KB |
Correct. |
2 |
Correct |
271 ms |
2044 KB |
Correct. |
3 |
Correct |
277 ms |
2092 KB |
Correct. |
4 |
Correct |
187 ms |
564 KB |
Correct. |
5 |
Correct |
183 ms |
560 KB |
Correct. |
6 |
Correct |
69 ms |
13740 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
54024 KB |
Correct. |
2 |
Correct |
179 ms |
1992 KB |
Correct. |
3 |
Correct |
157 ms |
1984 KB |
Correct. |
4 |
Correct |
170 ms |
1996 KB |
Correct. |
5 |
Correct |
134 ms |
564 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
1892 KB |
Correct. |
2 |
Correct |
132 ms |
1764 KB |
Correct. |
3 |
Correct |
163 ms |
1816 KB |
Correct. |
4 |
Correct |
193 ms |
12040 KB |
Correct. |
5 |
Correct |
82 ms |
588 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
149 ms |
1888 KB |
Correct. |
2 |
Correct |
104 ms |
1852 KB |
Correct. |
3 |
Correct |
67 ms |
11724 KB |
Correct. |
4 |
Correct |
131 ms |
9708 KB |
Correct. |
5 |
Correct |
134 ms |
536 KB |
Correct. |
6 |
Correct |
115 ms |
1884 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
1872 KB |
Correct. |
2 |
Correct |
23 ms |
2004 KB |
Correct. |
3 |
Correct |
1210 ms |
100856 KB |
Correct. |
4 |
Correct |
712 ms |
27204 KB |
Correct. |
5 |
Correct |
639 ms |
67212 KB |
Correct. |
6 |
Correct |
246 ms |
27832 KB |
Correct. |
7 |
Correct |
743 ms |
26552 KB |
Correct. |
8 |
Correct |
530 ms |
5004 KB |
Correct. |
9 |
Correct |
158 ms |
1864 KB |
Correct. |
10 |
Correct |
129 ms |
1840 KB |
Correct. |
11 |
Correct |
494 ms |
2152 KB |
Correct. |
12 |
Correct |
164 ms |
2052 KB |
Correct. |
13 |
Correct |
137 ms |
1952 KB |
Correct. |
14 |
Correct |
572 ms |
25924 KB |
Correct. |
15 |
Correct |
541 ms |
10180 KB |
Correct. |
16 |
Correct |
120 ms |
1712 KB |
Correct. |
17 |
Correct |
155 ms |
1960 KB |
Correct. |
18 |
Correct |
136 ms |
1928 KB |
Correct. |
19 |
Correct |
394 ms |
2036 KB |
Correct. |
20 |
Correct |
9 ms |
468 KB |
Correct. |
21 |
Correct |
11 ms |
1088 KB |
Correct. |
22 |
Correct |
17 ms |
3080 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
397 ms |
4624 KB |
Correct. |
2 |
Correct |
70 ms |
5180 KB |
Correct. |
3 |
Execution timed out |
3116 ms |
449536 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |