101312024-03-27 20:12:49111Vázsony vonatjegyet vásárolcpp17Hibás válasz 0/1001.583s50980 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++>50000000){
			return;
		}
		if(v[i]){
			return;
		}
		v[i]=1;
		a[ap++]=i;
		if(i==B){
			if(ap>bp){
				bp=ap;
				memcpy(b.data(),a.data(),ap*sizeof(int));
			}
		}
		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álasz279ms22176 KiB
subtask20/20
3Időlimit túllépés1.554s6400 KiB
4Időlimit túllépés1.552s28788 KiB
5Időlimit túllépés1.567s22920 KiB
6Elfogadva1.141s37988 KiB
7Időlimit túllépés1.574s23152 KiB
8Időlimit túllépés1.583s19096 KiB
9Időlimit túllépés1.569s37956 KiB
subtask30/15
10Időlimit túllépés1.575s19164 KiB
11Elfogadva9ms5488 KiB
12Hibás válasz1.08s5816 KiB
13Hibás válasz1.179s11840 KiB
14Időlimit túllépés1.567s12660 KiB
subtask40/20
15Hibás válasz760ms20848 KiB
16Időlimit túllépés1.557s19484 KiB
17Hibás válasz1.25s15952 KiB
18Hibás válasz1.202s23228 KiB
19Hibás válasz656ms12420 KiB
20Hibás válasz589ms20036 KiB
subtask50/45
21Hibás válasz555ms4776 KiB
22Időlimit túllépés1.55s50980 KiB
23Időlimit túllépés1.557s8212 KiB
24Időlimit túllépés1.554s20232 KiB
25Időlimit túllépés1.57s18036 KiB
26Időlimit túllépés1.562s26212 KiB
27Elfogadva217ms32708 KiB
28Időlimit túllépés1.575s41004 KiB
29Időlimit túllépés1.547s13592 KiB
30Időlimit túllépés1.569s35768 KiB
31Időlimit túllépés1.57s20984 KiB
32Időlimit túllépés1.547s8720 KiB
33Időlimit túllépés1.575s26580 KiB
34Időlimit túllépés1.565s32924 KiB
35Időlimit túllépés1.569s28672 KiB
36Időlimit túllépés1.565s25424 KiB
37Időlimit túllépés1.567s24236 KiB