Submission #80296

ソースコード

#include<bits/stdc++.h>
using namespace std;
int main(){
    //ofstream arrr("kariout.txt");
    int n,x,y;cin>>n>>x>>y;
    vector<vector<int>>s(n+1,vector<int>(0));
    for(int i=0;i<n-1;i++){
        int a,b;cin>>a>>b;
        s[a].push_back(b);
        s[b].push_back(a);
    }
    vector<int>t(n+1,INT_MAX);
    vector<int>mae(n+1,-1);
    t[x]=0;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<s[now].size();i++){
            if(t[now]+1 < t[s[now][i]]){
                t[s[now][i]]=t[now]+1;
                q.push(s[now][i]);
                mae[s[now][i]]=now;
            }
        }
    }
    cout<<t[y]<<"\n";
    int now=y;
    vector<int>v;
    while(now!=x){
        v.push_back(now);
        now=mae[now];
    }
    v.push_back(x);
    for(int i=v.size()-1;i>=0;i--){
        cout<<v[i]<<"\n";
    }
}

ステータス

項目	データ
問題	1819 - Path on tree
ユーザー名	ei2326
投稿日時	2024-08-05 12:08:09
言語	C++17
状態	Accepted
得点	101
ソースコード長	930 Byte
最大実行時間	55 ms
最大メモリ使用量	4468 KB

セット

	セット	得点	Cases
1	ALL	101 / 101	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in1.txt	AC	21 ms	600 KB	1
in2.txt	AC	21 ms	464 KB	1
in3.txt	AC	25 ms	568 KB	1
in4.txt	AC	43 ms	3732 KB	1
in5.txt	AC	54 ms	3616 KB	1
in6.txt	AC	43 ms	3624 KB	1
in7.txt	AC	46 ms	3752 KB	1
in8.txt	AC	46 ms	4240 KB	1
in9.txt	AC	55 ms	4468 KB	1
in10.txt	AC	49 ms	3764 KB	1
in11.txt	AC	29 ms	1460 KB	1
in12.txt	AC	19 ms	524 KB	1