101332024-03-27 20:24:06111Vázsony vonatjegyet vásárolcpp17Hibás válasz 0/1001.572s121584 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;
	int ansc=0,ac=0;
	vector<int>v(N+1),w(M);
	int st=clock();
	auto bt=[&](auto self,int i)->void{
		if(clock()-st>CLOCKS_PER_SEC)return;
		if(v[i]==0){
			ac++;
		}
		v[i]++;
		a.push_back(i);
		if(i==B){
			if(ac>ansc){
				ansc=ac;
				ans=a;
			}
		}
		else{
			for(auto[j,_,k]:g[i]){
				if(w[k]>=2){
					continue;
				}
				w[k]++;
				if(c[j]<=c[i]){
					self(self,j);
				}
				w[k]--;
			}
		}
		a.pop_back();
		v[i]--;
		if(v[i]==0){
			ac--;
		}
	};
	bt(bt,A);
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	cout<<ans.size()<<'\n';
	for(int i:ans){
		cout<<i<<' ';
	}
	cout<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Hibás válasz1.108s32568 KiB
subtask20/20
3Hibás válasz1.047s16824 KiB
4Hibás válasz1.31s83788 KiB
5Hibás válasz1.258s66356 KiB
6Hibás válasz1.203s52488 KiB
7Hibás válasz1.238s67240 KiB
8Hibás válasz1.21s52016 KiB
9Hibás válasz1.435s109108 KiB
subtask30/15
10Hibás válasz1.312s64192 KiB
11Elfogadva9ms9344 KiB
12Hibás válasz1.018s10260 KiB
13Hibás válasz1.054s20256 KiB
14Hibás válasz1.065s36208 KiB
subtask40/20
15Hibás válasz1.052s30876 KiB
16Hibás válasz1.159s47208 KiB
17Hibás válasz1.029s22928 KiB
18Hibás válasz1.054s29872 KiB
19Hibás válasz1.031s16488 KiB
20Hibás válasz1.06s26048 KiB
subtask50/45
21Hibás válasz1.003s7392 KiB
22Időlimit túllépés1.572s78712 KiB
23Hibás válasz1.037s20368 KiB
24Hibás válasz1.174s56064 KiB
25Hibás válasz1.159s48856 KiB
26Hibás válasz1.276s71352 KiB
27Elfogadva1.024s48268 KiB
28Hibás válasz1.486s121584 KiB
29Hibás válasz1.106s36032 KiB
30Hibás válasz1.424s102612 KiB
31Hibás válasz1.192s49212 KiB
32Hibás válasz1.039s23300 KiB
33Hibás válasz1.276s67080 KiB
34Hibás válasz1.274s60628 KiB
35Hibás válasz1.277s60668 KiB
36Hibás válasz1.279s60768 KiB
37Hibás válasz1.276s60920 KiB