結果
| 問題 | No.1565 Union |
| ユーザー |
 PCTprobability
|
| 提出日時 | 2021-06-26 13:20:07 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,054 ms / 2,000 ms |
| コード長 | 5,282 bytes |
| コンパイル時間 | 5,229 ms |
| コンパイル使用メモリ | 270,420 KB |
| 最終ジャッジ日時 | 2025-01-22 13:13:22 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:213:10: warning: division by zero [-Wdiv-by-zero]
213 | a=1/0;
| ~^~
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing ll = long long;using ld = long double;using ull = long long;#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))#define ALL(x) begin(x), end(x)#define all(s) (s).begin(),(s).end()#define rep2(i, m, n) for (int i = (m); i < (n); ++i)#define rep(i, n) rep2(i, 0, n)#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)#define rever(vec) reverse(vec.begin(), vec.end())#define sor(vec) sort(vec.begin(), vec.end())#define fi first#define se second#define P pair<ll,ll>#define REP(i, n) for (int i = 0; i < (n); ++i)//const ll mod = 998244353;const ll mod = 1000000007;const ll inf = 2000000000000000000ll;static const long double pi = 3.141592653589793;template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}void YesNo(bool a){if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}void YESNO(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}template<class T,class U> void chmax(T& t,const U& u){if(t<u) t=u;}template<class T,class U> void chmin(T& t,const U& u){if(t>u) t=u;}template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<typename T,typename ...Args>auto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector<T>(arg,x);else returnvector(arg,make_vector<T>(x,args...));}ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }void gbjsmzmfuuvdf(){ios::sync_with_stdio(false);std::cin.tie(nullptr);cout<< fixed << setprecision(20);}struct graph{struct edge{ll to,cost;};ll v;vector<vector<edge>> g;vector<ll> d;vector<bool> negative;vector<bool> diameter;vector<ll> topological_sort;ll diametercost;bool bipartitecheck;vector<ll> bipartite;graph(ll n){init(n);}void init(ll n){v=n;g.resize(n);d.resize(n);negative.resize(n);diameter.resize(n);bipartite.resize(n);for(int i=0;i<v;i++){d[i]=inf;bipartite[i]=-1;negative[i]=false;diameter[i]=false;}}void addedge(ll s,ll t,ll cost){edge e;e.to=t;e.cost=cost;g[s].push_back(e);}void dijkstra(ll s){for(int i=0;i<v;i++){d[i]=inf;}d[s]=0;priority_queue<P,vector<P>,greater<P>> que;que.push(P(0,s));while(!que.empty()){P p=que.top();que.pop();ll V=p.second;if(d[V]<p.first) continue;for(auto e:g[V]){if(d[e.to]>d[V]+e.cost){d[e.to]=d[V]+e.cost;que.push(P(d[e.to],e.to));}}}}void BellmanFord(ll s){for(int i=0;i<v;i++){d[i]=inf;negative[i]=false;}d[s]=0;for(int i=0;i<v;i++){for(int V=0;V<v;V++){if(d[V]==inf){continue;}for(auto e:g[V]){if(d[e.to]>d[V]+e.cost){d[e.to]=d[V]+e.cost;if(i==v-1){negative[e.to]=true;negative[V]=true;}}}}}}void dfs(ll s){for(int i=0;i<v;i++){d[i]=inf;}d[s]=0;dfs2(s,-1);}void dfs2(ll s,ll v){for(auto e:g[s]){if(e.to==v) continue;if(d[e.to]>d[s]+e.cost){d[e.to]=d[s]+e.cost;dfs2(e.to,s);}}}void treediameter(){dfs(0);ll p=0;ll q=0;for(int i=0;i<v;i++){if(q<d[i]){q=d[i];p=i;}}diameter[p]=true;dfs(p);ll p2=0;ll q2=0;for(int i=0;i<v;i++){if(q2<d[i]){q2=d[i];p2=i;}}diameter[p2]=true;diametercost=d[p2];}void Bipartite(){Bipartitedfs(0);}void Bipartitedfs(ll s,ll cur=0){bipartite[s]=cur;for(auto e:g[s]){if(bipartite[e.to]!=-1){if((bipartite[e.to]==bipartite[s])^(!e.cost%2)){bipartitecheck=false;}}else{if(e.cost%2){Bipartitedfs(e.to,1-cur);}else{Bipartitedfs(e.to,cur);}}}}void topologicalsort(){for(int i=0;i<v;i++){d[i]=0;}for(int i=0;i<v;i++){if(d[i]) continue;topologicaldfs(i);}rever(topological_sort);}void topologicaldfs(ll a){d[a]=1;for(auto e:g[a]){if(d[e.to]) continue;topologicaldfs(e.to);}topological_sort.push_back(a);}};int main() {gbjsmzmfuuvdf();ll n,m;map<P,ll> f;cin>>n>>m;assert(2<=n&&n<=200000&&2<=m&&m<=200000);graph g(n);for(int i=0;i<m;i++){ll a,b;cin>>a>>b;//assert(f[{a,b}]==0);if(f[{a,b}]){a=1/0;}assert(1<=a&&a<=n&&1<=b&&b<=n&&a!=b);f[{a,b}]++;f[{b,a}]++;a--;b--;g.addedge(a,b,1);g.addedge(b,a,1);}g.dijkstra(0);ifmax(g.d[n-1],inf/2);}