101302024-03-27 20:11:12111Vázsony vonatjegyet vásárolcpp17Hibás válasz 0/1001.6s98156 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<pair<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);
		g[b].emplace_back(a,w);
	}
	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>v(N+1),a(N+1),b(N+1);
	int ap=0,bp=0;
	int it=0;
	auto bt=[&](auto self,int i)->void{
		if(it++>100000000){
			return;
		}
		if(v[i]){
			return;
		}
		v[i]=1;
		a[ap++]=i;
		if(i==B){
			if(ap>bp){
				bp=ap;
				b=a;
			}
		}
		else{
			for(auto[j,_]:g[i]){
				if(c[j]<=c[i]){
					self(self,j);
				}
			}
		}
		ap--;
		v[i]=0;
	};
	bt(bt,A);
	b.resize(bp);
	sort(b.begin(),b.end());
	cout<<b.size()<<'\n';
	for(int i:b){
		cout<<i<<' ';
	}
	cout<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Hibás válasz293ms25084 KiB
subtask20/20
3Időlimit túllépés1.557s10576 KiB
4Időlimit túllépés1.587s41848 KiB
5Időlimit túllépés1.557s43288 KiB
6Elfogadva1.172s58300 KiB
7Időlimit túllépés1.549s50340 KiB
8Időlimit túllépés1.542s51072 KiB
9Időlimit túllépés1.542s81304 KiB
subtask30/15
10Időlimit túllépés1.549s66956 KiB
11Elfogadva9ms53524 KiB
12Időlimit túllépés1.6s51960 KiB
13Időlimit túllépés1.557s54940 KiB
14Időlimit túllépés1.554s60496 KiB
subtask40/20
15Időlimit túllépés1.544s68600 KiB
16Időlimit túllépés1.55s67236 KiB
17Időlimit túllépés1.565s56932 KiB
18Időlimit túllépés1.537s60556 KiB
19Hibás válasz1.287s60152 KiB
20Hibás válasz1.151s67548 KiB
subtask50/45
21Hibás válasz1.126s51960 KiB
22Időlimit túllépés1.559s98156 KiB
23Időlimit túllépés1.55s55748 KiB
24Időlimit túllépés1.583s67792 KiB
25Időlimit túllépés1.559s65716 KiB
26Időlimit túllépés1.567s73936 KiB
27Elfogadva237ms80772 KiB
28Időlimit túllépés1.565s89280 KiB
29Időlimit túllépés1.539s61836 KiB
30Időlimit túllépés1.572s83816 KiB
31Időlimit túllépés1.575s68896 KiB
32Időlimit túllépés1.575s57184 KiB
33Időlimit túllépés1.559s74892 KiB
34Időlimit túllépés1.569s77016 KiB
35Időlimit túllépés1.577s76744 KiB
36Időlimit túllépés1.565s73652 KiB
37Időlimit túllépés1.575s72468 KiB