100132024-03-24 09:17:47111Autópálya inflációcpp17Wrong answer 15/10068ms9520 KiB
#include <bits/stdc++.h>
using namespace std;

#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<array<double,2>>dp(N,{INFINITY,INFINITY});
	dp[0][0]=0;
	for(int i=0;i+1<N;i++){
		vector<int>v;
		for(int j=0;j<N;j++){
			if(i>0&&dp[j][i&1]>=dp[j][i&1^1]){
				dp[j][i&1]=dp[j][i&1^1];
				continue;
			}
			v.push_back(j);
		}
		for(int j:v){
			for(auto[k,w]:g[j]){
				dp[k][i&1^1]=min(dp[k][i&1^1],dp[j][i&1]+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
2Wrong answer64ms3456 KiB
subtask20/8
3Accepted59ms3528 KiB
4Wrong answer61ms3544 KiB
5Wrong answer61ms3868 KiB
6Accepted61ms3852 KiB
7Wrong answer59ms3828 KiB
subtask315/15
8Accepted3ms3132 KiB
9Accepted3ms3228 KiB
10Accepted3ms3272 KiB
11Accepted3ms3484 KiB
12Accepted3ms3584 KiB
13Accepted3ms3584 KiB
14Accepted3ms3808 KiB
15Accepted3ms4024 KiB
16Accepted3ms4124 KiB
17Accepted3ms4336 KiB
18Accepted3ms4344 KiB
subtask40/34
19Accepted63ms5652 KiB
20Wrong answer64ms5840 KiB
21Wrong answer64ms5880 KiB
22Accepted64ms6200 KiB
23Accepted63ms6360 KiB
24Wrong answer64ms6428 KiB
25Accepted61ms6272 KiB
26Accepted61ms6188 KiB
27Wrong answer64ms6344 KiB
28Wrong answer61ms6220 KiB
29Wrong answer61ms6268 KiB
30Wrong answer54ms6280 KiB
31Wrong answer61ms6332 KiB
32Wrong answer64ms6740 KiB
33Wrong answer64ms6764 KiB
subtask50/21
34Wrong answer6ms6032 KiB
35Accepted7ms6452 KiB
36Accepted7ms6524 KiB
37Accepted7ms6768 KiB
38Accepted7ms6744 KiB
39Accepted7ms6828 KiB
40Wrong answer8ms6836 KiB
41Wrong answer7ms6868 KiB
42Wrong answer4ms6800 KiB
43Wrong answer4ms6728 KiB
44Wrong answer4ms6876 KiB
45Wrong answer4ms6820 KiB
46Wrong answer4ms6720 KiB
47Wrong answer4ms6728 KiB
48Wrong answer6ms6892 KiB
49Wrong answer4ms6912 KiB
subtask60/22
50Wrong answer64ms8020 KiB
51Wrong answer64ms8064 KiB
52Accepted64ms8172 KiB
53Accepted64ms8296 KiB
54Accepted64ms8592 KiB
55Accepted64ms8656 KiB
56Wrong answer68ms8736 KiB
57Wrong answer67ms8824 KiB
58Wrong answer10ms8180 KiB
59Wrong answer61ms8668 KiB
60Wrong answer61ms8732 KiB
61Wrong answer61ms8700 KiB
62Wrong answer61ms8756 KiB
63Wrong answer61ms8812 KiB
64Wrong answer64ms9268 KiB
65Wrong answer64ms9444 KiB
66Wrong answer64ms9520 KiB