#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define double long double
const ll NMAX = 1e5 + 5;
vector<pair<ll,ll> > g[NMAX];
vector<vector<double> > dis(NMAX, vector<double>(31) );
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) {
for(long long i = 1; i <= n; i++){
g[i].clear();
for(long long j = 0; j <= 30; j++) dis[i][j] = 1e18;
}
h++;
for(long long i = 0; i < m; i++){
g[x[i] + 1].push_back({y[i] + 1, c[i]});
g[y[i] + 1].push_back({x[i] + 1, c[i]});
}
priority_queue<tuple<double,long long,long long>, vector<tuple<double,long long,long long> >, greater<tuple<double,long long,long long> > > q;
q.push({0, 1, 0});
dis[1][0] = 0;
while(!q.empty()){
auto [dist, v, u] = q.top();
q.pop();
if(dist > dis[v][u]) continue;
for(auto [to, cost] : g[v]){
if(arr[to - 1] == 2 and u < 30 and (dist + cost) / 2 < dis[to][u + 1]){
dis[to][u + 1] = ((double)dist + cost) / 2.0;
q.push({dis[to][u + 1], to, u + 1});
}
if(arr[to - 1] == 0 and dis[to][u] > 0){
dis[to][u] = 0;
q.push({dis[to][u], to, u});
}
if(dist + cost < dis[to][u]){
dis[to][u] = dist + cost;
q.push({dis[to][u], to, u});
}
}
}
double ans = 1e18;
for(long long i = 0; i <= k; i++) ans = min(ans, dis[h][i]);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
81 ms |
55528 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
78 ms |
55188 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
88 ms |
55380 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1979 ms |
59820 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
82 ms |
55380 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
87 ms |
55376 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
438 ms |
56320 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
529 ms |
56336 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |