結果
問題 | No.1565 Union |
ユーザー |
|
提出日時 | 2023-02-23 12:57:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 141 ms / 2,000 ms |
コード長 | 1,015 bytes |
コンパイル時間 | 932 ms |
コンパイル使用メモリ | 82,224 KB |
最終ジャッジ日時 | 2025-02-10 20:01:58 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<iostream>#include<vector>#include<queue>using namespace std;using ll=long long;#define rep(i,n) for(int i=0;i<n;i++)#define rrep(i,n) for(int i=(n)-1;i>=0;i--)#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;}template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N,M;cin>>N>>M;vector<vector<int>>g(N);rep(i,M){int a,b;cin>>a>>b;a--;b--;g[a].push_back(b);g[b].push_back(a);}vector<int>d(N,1<<30);d[0]=0;queue<pair<int,int>>q;q.push(make_pair(0,0));while(q.size()){auto[c,x]=q.front();q.pop();for(auto i:g[x]){if(chmin(d[i],c+1))q.push(make_pair(d[i],i));}}if(d[N-1]==1<<30)cout<<-1<<"\n";else cout<<d[N-1]<<"\n";}