10012 | 2024-03-24 09:08:40 | 111 | Autópálya infláció | cpp17 | Futási hiba 15/100 | 256ms | 262808 KiB |
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
#define int long long
#define double long double
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M;
cin>>N>>M;
vector<vector<pair<int,int>>>g(N);
for(int i=0;i<M;i++){
int a,b,c;
cin>>a>>b>>c;
a--,b--;
g[a].emplace_back(b,c);
g[b].emplace_back(a,c);
}
vector<vector<double>>dp(N,vector<double>(N,INFINITY));
dp[0][0]=0;
for(int i=0;i+1<N;i++){
for(int j=0;j<N;j++){
if(dp[j][i]==INFINITY){
continue;
}
for(auto[k,w]:g[j]){
dp[k][i+1]=min(dp[k][i+1],dp[j][i]+w*pow(2,i));
}
}
}
for(int i=1;i<N;i++){
cout<<fixed<<setprecision(0)<<fmod(*min_element(dp[i].begin(),dp[i].end()),1000000007)<<'\n';
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1892 KiB | ||||
2 | Futási hiba | 100ms | 262808 KiB | ||||
subtask2 | 0/8 | ||||||
3 | Futási hiba | 119ms | 262556 KiB | ||||
4 | Futási hiba | 100ms | 262428 KiB | ||||
5 | Futási hiba | 122ms | 262172 KiB | ||||
6 | Futási hiba | 97ms | 261916 KiB | ||||
7 | Futási hiba | 119ms | 261664 KiB | ||||
subtask3 | 15/15 | ||||||
8 | Elfogadva | 3ms | 3588 KiB | ||||
9 | Elfogadva | 3ms | 3564 KiB | ||||
10 | Elfogadva | 3ms | 3688 KiB | ||||
11 | Elfogadva | 3ms | 3908 KiB | ||||
12 | Elfogadva | 3ms | 4124 KiB | ||||
13 | Elfogadva | 3ms | 4208 KiB | ||||
14 | Elfogadva | 3ms | 4216 KiB | ||||
15 | Elfogadva | 3ms | 4312 KiB | ||||
16 | Elfogadva | 3ms | 4440 KiB | ||||
17 | Elfogadva | 2ms | 4528 KiB | ||||
18 | Elfogadva | 3ms | 4772 KiB | ||||
subtask4 | 0/34 | ||||||
19 | Futási hiba | 100ms | 260364 KiB | ||||
20 | Futási hiba | 120ms | 260360 KiB | ||||
21 | Futási hiba | 97ms | 260356 KiB | ||||
22 | Futási hiba | 97ms | 260148 KiB | ||||
23 | Futási hiba | 97ms | 260180 KiB | ||||
24 | Futási hiba | 97ms | 260160 KiB | ||||
25 | Futási hiba | 97ms | 260148 KiB | ||||
26 | Futási hiba | 97ms | 260152 KiB | ||||
27 | Futási hiba | 97ms | 260144 KiB | ||||
28 | Futási hiba | 119ms | 259900 KiB | ||||
29 | Futási hiba | 97ms | 259888 KiB | ||||
30 | Hibás válasz | 256ms | 250960 KiB | ||||
31 | Futási hiba | 118ms | 259896 KiB | ||||
32 | Futási hiba | 120ms | 259860 KiB | ||||
33 | Futási hiba | 96ms | 259824 KiB | ||||
subtask5 | 0/21 | ||||||
34 | Hibás válasz | 35ms | 12796 KiB | ||||
35 | Elfogadva | 82ms | 13208 KiB | ||||
36 | Elfogadva | 85ms | 13232 KiB | ||||
37 | Elfogadva | 83ms | 13332 KiB | ||||
38 | Elfogadva | 90ms | 13432 KiB | ||||
39 | Elfogadva | 83ms | 13388 KiB | ||||
40 | Hibás válasz | 71ms | 13448 KiB | ||||
41 | Hibás válasz | 72ms | 13688 KiB | ||||
42 | Hibás válasz | 16ms | 13236 KiB | ||||
43 | Hibás válasz | 14ms | 13264 KiB | ||||
44 | Hibás válasz | 16ms | 13404 KiB | ||||
45 | Hibás válasz | 14ms | 13464 KiB | ||||
46 | Hibás válasz | 16ms | 13372 KiB | ||||
47 | Hibás válasz | 14ms | 12732 KiB | ||||
48 | Hibás válasz | 24ms | 13260 KiB | ||||
49 | Hibás válasz | 25ms | 13284 KiB | ||||
subtask6 | 0/22 | ||||||
50 | Futási hiba | 97ms | 259576 KiB | ||||
51 | Futási hiba | 119ms | 259564 KiB | ||||
52 | Futási hiba | 97ms | 259556 KiB | ||||
53 | Futási hiba | 122ms | 259528 KiB | ||||
54 | Futási hiba | 98ms | 259272 KiB | ||||
55 | Futási hiba | 97ms | 259232 KiB | ||||
56 | Futási hiba | 97ms | 259224 KiB | ||||
57 | Futási hiba | 97ms | 259216 KiB | ||||
58 | Hibás válasz | 57ms | 37064 KiB | ||||
59 | Futási hiba | 97ms | 259216 KiB | ||||
60 | Futási hiba | 96ms | 259204 KiB | ||||
61 | Futási hiba | 118ms | 259196 KiB | ||||
62 | Futási hiba | 96ms | 259192 KiB | ||||
63 | Futási hiba | 119ms | 259176 KiB | ||||
64 | Futási hiba | 98ms | 259172 KiB | ||||
65 | Futási hiba | 120ms | 259168 KiB | ||||
66 | Futási hiba | 122ms | 259144 KiB |