#include <bits/stdc++.h>
using namespace std;
bool vis[100005];
vector<pair<int,int> > G[100005];
vector<int> arr1;
bool ima_pat(int teme, int kraj) {
if (teme==kraj)
return true;
vis[teme]=1;
bool ok=false;
for (auto next:G[teme])
if (!vis[next.first])
ok=(ok|ima_pat(next.first,kraj));
return ok;
}
double rez=1e18, dp[100005][35];
void f(int teme, int kraj, double vreme, int k) {
if (dp[teme][k]<=vreme)
return;
dp[teme][k]=vreme;
for (auto next:G[teme]) {
if (k>0&&arr1[next.first]==0)
f(next.first, kraj, 0, k-1);
else if (k>0&&arr1[next.first]==2)
f(next.first, kraj, vreme/2.0, k-1);
f(next.first, kraj, vreme+next.second, k);
}
}
double solve(int n, int m, int k, int h, vector<int> a, vector<int> b, vector<int> c, vector<int> arr) {
for (int i=0;i<m;i++) {
G[a[i]].push_back({b[i],c[i]});
G[b[i]].push_back({a[i],c[i]});
}
arr1=arr;
for (int i=0;i<n;i++)
vis[i]=0;
for (int i=0;i<n;i++)
for (int j=0;j<35;j++)
dp[i][j]=1e18;
if (!ima_pat(0,h)) return -1;
f(0, h, 0, k);
double r=1e18;
for (int i=0;i<35;i++)
r=min(r,dp[h][i]);
return r;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3072 ms |
3352 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3063 ms |
6324 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3038 ms |
5708 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3063 ms |
30044 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3058 ms |
6068 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3038 ms |
5716 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3027 ms |
5916 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3035 ms |
5744 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |