100122024-03-24 09:08:40111Autópálya inflációcpp17Runtime error 15/100256ms262808 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1892 KiB
2Runtime error100ms262808 KiB
subtask20/8
3Runtime error119ms262556 KiB
4Runtime error100ms262428 KiB
5Runtime error122ms262172 KiB
6Runtime error97ms261916 KiB
7Runtime error119ms261664 KiB
subtask315/15
8Accepted3ms3588 KiB
9Accepted3ms3564 KiB
10Accepted3ms3688 KiB
11Accepted3ms3908 KiB
12Accepted3ms4124 KiB
13Accepted3ms4208 KiB
14Accepted3ms4216 KiB
15Accepted3ms4312 KiB
16Accepted3ms4440 KiB
17Accepted2ms4528 KiB
18Accepted3ms4772 KiB
subtask40/34
19Runtime error100ms260364 KiB
20Runtime error120ms260360 KiB
21Runtime error97ms260356 KiB
22Runtime error97ms260148 KiB
23Runtime error97ms260180 KiB
24Runtime error97ms260160 KiB
25Runtime error97ms260148 KiB
26Runtime error97ms260152 KiB
27Runtime error97ms260144 KiB
28Runtime error119ms259900 KiB
29Runtime error97ms259888 KiB
30Wrong answer256ms250960 KiB
31Runtime error118ms259896 KiB
32Runtime error120ms259860 KiB
33Runtime error96ms259824 KiB
subtask50/21
34Wrong answer35ms12796 KiB
35Accepted82ms13208 KiB
36Accepted85ms13232 KiB
37Accepted83ms13332 KiB
38Accepted90ms13432 KiB
39Accepted83ms13388 KiB
40Wrong answer71ms13448 KiB
41Wrong answer72ms13688 KiB
42Wrong answer16ms13236 KiB
43Wrong answer14ms13264 KiB
44Wrong answer16ms13404 KiB
45Wrong answer14ms13464 KiB
46Wrong answer16ms13372 KiB
47Wrong answer14ms12732 KiB
48Wrong answer24ms13260 KiB
49Wrong answer25ms13284 KiB
subtask60/22
50Runtime error97ms259576 KiB
51Runtime error119ms259564 KiB
52Runtime error97ms259556 KiB
53Runtime error122ms259528 KiB
54Runtime error98ms259272 KiB
55Runtime error97ms259232 KiB
56Runtime error97ms259224 KiB
57Runtime error97ms259216 KiB
58Wrong answer57ms37064 KiB
59Runtime error97ms259216 KiB
60Runtime error96ms259204 KiB
61Runtime error118ms259196 KiB
62Runtime error96ms259192 KiB
63Runtime error119ms259176 KiB
64Runtime error98ms259172 KiB
65Runtime error120ms259168 KiB
66Runtime error122ms259144 KiB