結果
問題 | No.1565 Union |
ユーザー |
|
提出日時 | 2021-06-26 13:49:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 827 ms / 2,000 ms |
コード長 | 3,278 bytes |
コンパイル時間 | 2,718 ms |
コンパイル使用メモリ | 216,164 KB |
最終ジャッジ日時 | 2025-01-22 13:17:44 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define MOD 1000000007#define MOD2 998244353#define rep(i,n) for (int i = 0; i < (int)(n); i++)#define reps(i,s,n) for (int i = (int)(s); i < (int)(n); i++)#define repit(i,C) for (auto i = (C).begin(); i != (C).end(); i++)#define pr(a) cout << a#define prl(a) cout << (a) << endl#define prld(a) cout << setprecision(15)<< (a) << endl#define allrange(a) a.begin(),a.end()template<typename T = int>struct Edge {int src, dst;T weight;Edge(int src, int dst, T weight) :src(src), dst(dst), weight(weight) { };Edge() {};};template<typename T = int>bool operator < (const Edge<T> &e, const Edge<T> &f) {return e.weight != f.weight ? e.weight < f.weight : // コストが低いほう優先e.src != f.src ? e.src < f.src : e.dst < f.dst;};template <typename T= int>using Edges = std::vector<Edge<T>>;using Vertexs = std::vector<int>;template<typename T = int>struct Graph { //directed graphVertexs vertexs;map<int,int> vindex;Edges<T> edges;std::vector<std::vector<std::pair<T,int>>> adjacent_to, adjacent_from;Graph(): vertexs(Vertexs (0)),edges(Edges<T>(0)),vindex(),adjacent_to(std::vector<std::vector<std::pair<T,int>>>(0)),adjacent_from(std::vector<std::vector<std::pair<T,int>>>(0)) {};void addv(int t){vertexs.push_back(t);vindex[t]=vertexs.size()-1;adjacent_to.push_back(std::vector<std::pair<T,int>>(0));adjacent_from.push_back(std::vector<std::pair<T,int>>(0));}void adde(int s,int d,T w){edges.push_back(Edge<T>(s,d,w));adjacent_to.at(vindex[s]).push_back(std::make_pair(w,d));adjacent_from.at(vindex[s]).push_back(std::make_pair(w,d));}};template<typename T = int>struct UndirectedGraph : Graph<T>{ //undirected graphvoid adde(int s,int d,T w){this.adde(s,d,w);this.adjacent_to.at(d).push_back(std::make_pair(w,s));this.adjacent_from.at(d).push_back(std::make_pair(w,s));}};/* 2021/06/20unordered_setを使って拡張可能なデータ構造。find 所属判定insert 元の挿入が平均o(1)で可能。グループの合併は再帰関数を使用元の削除はできない*/vector<int> graph_bfs(struct Graph<int>& G,int s=0){int N = G.vertexs.size();vector<int> out(N);vector<bool> visited(N);queue<int> work;for(int i=0;i<N;i++){out[i]=INT_MAX;visited[i]=false;}out[s]=0;work.push(s);while(!work.empty()){int pt = work.front();work.pop();for(auto e:G.adjacent_from[pt])if(out[e.second]==INT_MAX) out[e.second]=out[pt]+e.first;else out[e.second] = min(out[e.second],out[pt]+e.first);if(visited[pt]) continue;visited[pt]=true;for(auto e:G.adjacent_from[pt])if(!visited[e.second]) work.push(e.second);}for(int &l:out) if(l==INT_MAX) l=-1;return out;};int main(){//1変数入力int N,M;cin >> N >> M;Graph<int> G;rep(i,N) G.addv(i);rep(i,M){int u,v;cin >> u >> v;u--;v--;G.adde(u,v,1);G.adde(v,u,1);}auto ans = graph_bfs(G,0);prl(ans[N-1]);}