結果
問題 | No.1565 Union |
ユーザー |
![]() |
提出日時 | 2021-04-21 10:22:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 240 ms / 2,000 ms |
コード長 | 2,417 bytes |
コンパイル時間 | 2,326 ms |
コンパイル使用メモリ | 203,504 KB |
最終ジャッジ日時 | 2025-01-20 22:27:34 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;constexpr int Inf = 2000000030;constexpr ll INF= 2000000000000000001;constexpr ll MOD = 1000000007;const double PI = 3.14159265358979323846;typedef pair<ll,ll> P;typedef pair<ll,P> PP;template<typename T>vector<T> make_vector(size_t s) {return vector<T>(s);}template<typename T,typename... Args>auto make_vector(size_t s,Args... args) {return vector(s,make_vector<T>(args...));}template<typename T> inline bool chmax(T &a, T b) {if (a < b) {a = b;return 1;}return 0;}template<typename T> inline bool chmin(T &a, T b) {if (a > b) {a = b;return 1;}return 0;}ll mod(ll val, ll M) {val = val % M;if(val < 0) {val += M;}return val;}template<typename T>T modpow(T N, T P, T M){if(P == 0) return 1;if(P < 0) return 0;if(P % 2 == 0){ll t = RS(N, P/2, M);if(M == -1) return t * t;return t * t % M;}if(M == -1) return N * modpow(N,P - 1,M);return N * modpow(N, P-1, M) % M;}struct edge{int to;ll cost;};int N; //頂点数vector<edge> graph[200010];ll dist[200010]; //頂点sからの最短距離int pre[200010];void Dijkstra(int s) {//greater<P>を指定することでfirstが小さい順に取り出せるpriority_queue<P,vector<P>,greater<P>> que;fill(dist,dist + N,INF);fill(pre,pre + N,-1);dist[s] = 0;que.push(P(0,s));while(!que.empty()) {P p = que.top();que.pop();int v = p.second;if(dist[v] < p.first) {continue;}for(auto x:graph[v]) {if(chmin(dist[x.to],dist[v] + x.cost)) {pre[x.to] = v;que.push(P(dist[x.to],x.to));}}}}//最短路を取得vector<int> get_path(int t) {vector<int> path;while(t != -1) {path.push_back(t);t = pre[t];}reverse(path.begin(),path.end());return path;}int main() {cin >> N;int M;cin >> M;for(int i = 0;i < M;i++) {int a,b;cin >> a >> b;a--;b--;graph[a].push_back(edge{b,1});graph[b].push_back(edge{a,1});}Dijkstra(0);if(dist[N - 1] == INF) cout << -1 << endl;else cout << dist[N - 1] << endl;}