101322024-03-27 20:18:50111Vázsony vonatjegyet vásárolcpp17Időlimit túllépés 0/1001.6s75456 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define INF (int)1e18

template<typename T>
using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M,A,B;
	cin>>N>>M>>A>>B;
	vector<vector<tuple<int,int,int>>>g(N+1);
	for(int i=0;i<M;i++){
		int a,b,w;
		cin>>a>>b>>w;
		g[a].emplace_back(b,w,i);
		g[b].emplace_back(a,w,i);
	}
	vector<int>c(N+1,INF);
	min_priority_queue<pair<int,int>>pq;
	c[B]=0;
	pq.emplace(0,B);
	while(!pq.empty()){
		auto[d,i]=pq.top();
		pq.pop();
		if(d>c[i]){
			continue;
		}
		for(auto[j,w,_]:g[i]){
			if(c[i]+w<c[j]){
				c[j]=c[i]+w;
				pq.emplace(c[j],j);
			}
		}
	}
	vector<int>ans,a;
	vector<int>v(M);
	auto bt=[&](auto self,int i)->void{
		a.push_back(i);
		if(i==B){
			vector<int>aa(a);
			sort(aa.begin(),aa.end());
			aa.erase(unique(aa.begin(),aa.end()),aa.end());
			if(aa.size()>ans.size()){
				ans=aa;
			}
		}
		else{
			for(auto[j,_,k]:g[i]){
				if(v[k]>=2){
					continue;
				}
				v[k]++;
				if(c[j]<=c[i]){
					self(self,j);
				}
				v[k]--;
			}
		}
		a.pop_back();
	};
	bt(bt,A);
	cout<<ans.size()<<'\n';
	for(int i:ans){
		cout<<i<<' ';
	}
	cout<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1832 KiB
2Időlimit túllépés1.6s16232 KiB
subtask20/20
3Időlimit túllépés1.557s8280 KiB
4Időlimit túllépés1.58s41552 KiB
5Időlimit túllépés1.575s33192 KiB
6Időlimit túllépés1.542s24876 KiB
7Időlimit túllépés1.569s32628 KiB
8Időlimit túllépés1.557s25180 KiB
9Időlimit túllépés1.574s53492 KiB
subtask30/15
10Időlimit túllépés1.567s31888 KiB
11Elfogadva9ms6352 KiB
12Időlimit túllépés1.552s4900 KiB
13Időlimit túllépés1.567s9976 KiB
14Időlimit túllépés1.55s18136 KiB
subtask40/20
15Időlimit túllépés1.57s15260 KiB
16Időlimit túllépés1.587s22772 KiB
17Időlimit túllépés1.574s10964 KiB
18Időlimit túllépés1.557s14352 KiB
19Időlimit túllépés1.57s7628 KiB
20Időlimit túllépés1.55s12680 KiB
subtask50/45
21Időlimit túllépés1.554s4568 KiB
22Időlimit túllépés1.575s75456 KiB
23Időlimit túllépés1.562s10524 KiB
24Időlimit túllépés1.555s28192 KiB
25Időlimit túllépés1.559s24560 KiB
26Időlimit túllépés1.552s35396 KiB
27Elfogadva609ms45008 KiB
28Időlimit túllépés1.569s60936 KiB
29Időlimit túllépés1.564s18368 KiB
30Időlimit túllépés1.531s51332 KiB
31Időlimit túllépés1.559s24432 KiB
32Időlimit túllépés1.582s12024 KiB
33Időlimit túllépés1.575s33556 KiB
34Időlimit túllépés1.578s30228 KiB
35Időlimit túllépés1.562s30220 KiB
36Időlimit túllépés1.57s30320 KiB
37Időlimit túllépés1.554s30280 KiB