100122024-03-24 09:08:40111Autópálya inflációcpp17Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1892 KiB
2Futási hiba100ms262808 KiB
subtask20/8
3Futási hiba119ms262556 KiB
4Futási hiba100ms262428 KiB
5Futási hiba122ms262172 KiB
6Futási hiba97ms261916 KiB
7Futási hiba119ms261664 KiB
subtask315/15
8Elfogadva3ms3588 KiB
9Elfogadva3ms3564 KiB
10Elfogadva3ms3688 KiB
11Elfogadva3ms3908 KiB
12Elfogadva3ms4124 KiB
13Elfogadva3ms4208 KiB
14Elfogadva3ms4216 KiB
15Elfogadva3ms4312 KiB
16Elfogadva3ms4440 KiB
17Elfogadva2ms4528 KiB
18Elfogadva3ms4772 KiB
subtask40/34
19Futási hiba100ms260364 KiB
20Futási hiba120ms260360 KiB
21Futási hiba97ms260356 KiB
22Futási hiba97ms260148 KiB
23Futási hiba97ms260180 KiB
24Futási hiba97ms260160 KiB
25Futási hiba97ms260148 KiB
26Futási hiba97ms260152 KiB
27Futási hiba97ms260144 KiB
28Futási hiba119ms259900 KiB
29Futási hiba97ms259888 KiB
30Hibás válasz256ms250960 KiB
31Futási hiba118ms259896 KiB
32Futási hiba120ms259860 KiB
33Futási hiba96ms259824 KiB
subtask50/21
34Hibás válasz35ms12796 KiB
35Elfogadva82ms13208 KiB
36Elfogadva85ms13232 KiB
37Elfogadva83ms13332 KiB
38Elfogadva90ms13432 KiB
39Elfogadva83ms13388 KiB
40Hibás válasz71ms13448 KiB
41Hibás válasz72ms13688 KiB
42Hibás válasz16ms13236 KiB
43Hibás válasz14ms13264 KiB
44Hibás válasz16ms13404 KiB
45Hibás válasz14ms13464 KiB
46Hibás válasz16ms13372 KiB
47Hibás válasz14ms12732 KiB
48Hibás válasz24ms13260 KiB
49Hibás válasz25ms13284 KiB
subtask60/22
50Futási hiba97ms259576 KiB
51Futási hiba119ms259564 KiB
52Futási hiba97ms259556 KiB
53Futási hiba122ms259528 KiB
54Futási hiba98ms259272 KiB
55Futási hiba97ms259232 KiB
56Futási hiba97ms259224 KiB
57Futási hiba97ms259216 KiB
58Hibás válasz57ms37064 KiB
59Futási hiba97ms259216 KiB
60Futási hiba96ms259204 KiB
61Futási hiba118ms259196 KiB
62Futási hiba96ms259192 KiB
63Futási hiba119ms259176 KiB
64Futási hiba98ms259172 KiB
65Futási hiba120ms259168 KiB
66Futási hiba122ms259144 KiB