提出 #68169694

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
bool st;
using namespace std;
template<typename T>istream&operator>>(istream&I,vector<T>&v){for(auto&i:v)I>>i;return I;}
template<typename T>ostream&operator<<(ostream&O,vector<T> v){for(auto i:v)O<<i<<' ';return O;}
string TMP,STR;
stringstream CIN;
void read_all(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#ifdef debug
	cerr<<"----------------------------------- START -----------------------------------\n";
	while(getline(cin,TMP))STR+=TMP,STR+='\n';
	CIN.str(STR);
	cerr<<"\n--------------------------------- INPUT END ---------------------------------\n";
#endif
}
#ifdef debug
#define cin CIN
#endif
namespace AC{
int n,m,x,y;
vector<int>g[1010];
bool vis[1010];
int vis2[1010];
int ans[1010],cnt;
bool ed=0;
bool can[1010][1010];
void dfs(){
	int u=ans[cnt-1];
	if(vis[u])return;
	vis[u]=1;
	if(vis2[u])return;
	if(u==y){
		for(int i=0;i<cnt;i++)cout<<ans[i]<<' ';
		cout<<'\n';
		ed=1;
		return;
	}
	for(auto v:g[u])if(can[u][v]){
		ans[cnt++]=v;
		dfs();
		cnt--;
		if(ed)return;
	}
	else vis2[v]++;
	for(auto v:g[u])if(!can[u][v])vis2[v]--;
	vis[u]=0;
}
void init(int x,int u){
	if(can[x][u])return;
	if(u==x)return;
	can[x][u]=1;
	for(auto v:g[u])init(x,v);
}
void solve(){
	ed=0;
	cin>>n>>m>>x>>y;
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)can[i][j]=0;
	for(int i=0;i<1010;i++)g[i].clear(),vis[i]=0,vis2[i]=0;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		init(i,y);
	}
	for(int i=1;i<=n;i++)sort(all(g[i]));
	cnt=0;
	ans[cnt++]=x;
	dfs();
}
}
bool ed;
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	chrono::steady_clock::time_point St=chrono::steady_clock::now();
	read_all();
	chrono::steady_clock::time_point ST=chrono::steady_clock::now();
	int t=1;
	cin>>t;
	while(t--)AC::solve();
	chrono::steady_clock::time_point ED=chrono::steady_clock::now();
	cerr<<setprecision(3)<<fixed<<"\n\n------------------------------------ END ------------------------------------\n"<<"Total Time   : "<<left<<setw(10)<<chrono::duration_cast<chrono::milliseconds>(ED-St).count()<<" \tms\n"<<"Real  Time   : "<<left<<setw(10)<<chrono::duration_cast<chrono::milliseconds>(ED-ST).count()<<" \tms\n"<<"             : "<<left<<setw(10)<<chrono::duration_cast<chrono::microseconds>(ED-ST).count()<<" \tμs\n\n"<<"Total Memory : "<<left<<setw(10)<<(&ed-&st)/1048576.0<<" \tMB\n"<<"               "<<left<<setw(10)<<(&ed-&st)/1024.0<<" \tKB\n"<<"               "<<left<<setw(10)<<(&ed-&st)<<" \tByte\n";
}

提出情報

ジャッジ結果