100132024-03-24 09:17:47111Autópálya inflációcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1892 KiB
2Hibás válasz64ms3456 KiB
subtask20/8
3Elfogadva59ms3528 KiB
4Hibás válasz61ms3544 KiB
5Hibás válasz61ms3868 KiB
6Elfogadva61ms3852 KiB
7Hibás válasz59ms3828 KiB
subtask315/15
8Elfogadva3ms3132 KiB
9Elfogadva3ms3228 KiB
10Elfogadva3ms3272 KiB
11Elfogadva3ms3484 KiB
12Elfogadva3ms3584 KiB
13Elfogadva3ms3584 KiB
14Elfogadva3ms3808 KiB
15Elfogadva3ms4024 KiB
16Elfogadva3ms4124 KiB
17Elfogadva3ms4336 KiB
18Elfogadva3ms4344 KiB
subtask40/34
19Elfogadva63ms5652 KiB
20Hibás válasz64ms5840 KiB
21Hibás válasz64ms5880 KiB
22Elfogadva64ms6200 KiB
23Elfogadva63ms6360 KiB
24Hibás válasz64ms6428 KiB
25Elfogadva61ms6272 KiB
26Elfogadva61ms6188 KiB
27Hibás válasz64ms6344 KiB
28Hibás válasz61ms6220 KiB
29Hibás válasz61ms6268 KiB
30Hibás válasz54ms6280 KiB
31Hibás válasz61ms6332 KiB
32Hibás válasz64ms6740 KiB
33Hibás válasz64ms6764 KiB
subtask50/21
34Hibás válasz6ms6032 KiB
35Elfogadva7ms6452 KiB
36Elfogadva7ms6524 KiB
37Elfogadva7ms6768 KiB
38Elfogadva7ms6744 KiB
39Elfogadva7ms6828 KiB
40Hibás válasz8ms6836 KiB
41Hibás válasz7ms6868 KiB
42Hibás válasz4ms6800 KiB
43Hibás válasz4ms6728 KiB
44Hibás válasz4ms6876 KiB
45Hibás válasz4ms6820 KiB
46Hibás válasz4ms6720 KiB
47Hibás válasz4ms6728 KiB
48Hibás válasz6ms6892 KiB
49Hibás válasz4ms6912 KiB
subtask60/22
50Hibás válasz64ms8020 KiB
51Hibás válasz64ms8064 KiB
52Elfogadva64ms8172 KiB
53Elfogadva64ms8296 KiB
54Elfogadva64ms8592 KiB
55Elfogadva64ms8656 KiB
56Hibás válasz68ms8736 KiB
57Hibás válasz67ms8824 KiB
58Hibás válasz10ms8180 KiB
59Hibás válasz61ms8668 KiB
60Hibás válasz61ms8732 KiB
61Hibás válasz61ms8700 KiB
62Hibás válasz61ms8756 KiB
63Hibás válasz61ms8812 KiB
64Hibás válasz64ms9268 KiB
65Hibás válasz64ms9444 KiB
66Hibás válasz64ms9520 KiB