提出 #68164887

---

ソースコード 拡げる

#include<fstream>
#include<iostream>
#include<iomanip>
#include<vector>
#include<queue>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<cmath>
#include<numbers>
#include<algorithm>
#include<string>
#include<set>
#include<stack>
#include<random>
#include<bitset>
#include<cassert>
#include<exception>

using namespace std;
using ll=long long;
using uset=unordered_set<long long>;

int H,W;
vector<string> strs;

struct point{
	int x,y;
	point():x(0),y(0){}
	point(int x,int y):x(x),y(y){}

	point operator+(const point& a){
		return point(a.x+x,a.y+y);
	}
	bool rangeCheck(){
		return 0<=x&&x<W&&0<=y&&y<H;
	}
	bool mapCheck(){
		return rangeCheck()&&strs[y][x]=='.';
	}
	bool operator<(const point& a)const{
		if(x!=a.x)return x<a.x;
		return y<a.y;
	}
};

template<typename T>
bool chmax(T& a,const T& b){
	if(a<b){
		a=b;
		return true;
	}
	return false;
}
template<typename T>
bool chmin(T& a,const T& b){
	if(a>b){
		a=b;
		return true;
	}
	return false;
}

int main(){
	vector<vector<int>> aans;
	int T;
	cin>>T;

	while(T--){
		int N,M,X,Y;
		cin>>N>>M>>X>>Y;
		X--;Y--;
		
		vector graph(N,vector<int>());
		for(int i=0;i<M;i++){
			int a,b;
			cin>>a>>b;
			a--;b--;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}
		for(int i=0;i<N;i++){
			sort(graph[i].rbegin(),graph[i].rend());
		}

		stack<point> st;
		vector<int> visited(N, -32915);
		st.push({X,-1});

		while(!st.empty()){
			auto v=st.top();
			st.pop();
			if(visited[v.x]!=-32915)continue;
			visited[v.x]=v.y;

			if(v.x==Y){
				break;
			}	
			
			for(int u:graph[v.x]){
				if(visited[u]==-32915){
					st.push({u,v.x});
				}
			}
		}
		vector<int> ans;
		int t=Y;
		while(t!=-1){
			ans.push_back(t+1);
			t=visited[t];
		}

		reverse(ans.begin(), ans.end());
		aans.push_back(ans);
	}

	for(auto& v:aans){
		for(auto & i:v){
			cout<<i<<" ";
		}
		cout<<endl;
	}

	return 0;
}

提出情報

ジャッジ結果