結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:50:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 253 ms / 2,000 ms |
コード長 | 4,839 bytes |
コンパイル時間 | 4,297 ms |
コンパイル使用メモリ | 262,080 KB |
実行使用メモリ | 48,604 KB |
最終ジャッジ日時 | 2025-09-06 13:50:32 |
合計ジャッジ時間 | 9,419 ms |
ジャッジサーバーID (参考情報) |
judge / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
// https://qiita.com/Raclamusi/items/660f0f42c57e4371ed78 #ifdef INCLUDED_MAIN struct Edge { ll to; ll cost; }; using Graph = vector<vector<Edge>>; using P = pair<ll, ll>; // const ll INF = 1LL << 60; /* dijkstra(G,s,dis,prev) 入力:グラフ G, 開始点 s, 距離を格納する dis, 最短経路の前の点を記録するprev 計算量:O(|E|log|V|) 副作用:dis, prevが書き換えられる 使用法 ``` //初期化は自動でされる vector<ll> dis, prev; dijkstra(G, r, dis, prev); ``` */ void dijkstra(const Graph &G, ll s, vector<ll> &dis, vector<ll> &prev) { ll N = G.size(); dis.resize(N, INF); prev.resize(N, -1); // 初期化 priority_queue<P, vector<P>, greater<P>> pq; dis[s] = 0; pq.emplace(dis[s], s); while (!pq.empty()) { P p = pq.top(); pq.pop(); ll v = p.second; if (dis[v] < p.first) { continue; } for (auto &e : G[v]) { if (dis[e.to] > dis[v] + e.cost) { dis[e.to] = dis[v] + e.cost; prev[e.to] = v; // 頂点 v を通って e.to にたどり着いた pq.emplace(dis[e.to], e.to); } } } } /* get_path(prev, t) 入力:dijkstra で得た prev, ゴール t 出力: t への最短路のパス */ vector<ll> get_path(const vector<ll> &prev, ll t) { vector<ll> path; for (ll cur = t; cur != -1; cur = prev[cur]) { path.push_back(cur); } reverse(path.begin(), path.end()); // 逆順なのでひっくり返す return path; } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); // ref:https://rsk0315.hatenablog.com/entry/2020/05/09/170315 // ll T; // cin >> T; // rep(i, T)solve(); // failed to analyze input format // TODO: edit here ll N, M; cin >> N >> M; vc<ll> U(M), V(M); rep(i, M) { std::cin >> U[i] >> V[i]; } ll K; cin >> K; vc<ll> A(N, 0); rep(i, K) { ll a; cin >> a; a--; A[a]++; } vc<vc<Edge>> G(5 * N); rep(i, M) { ll u = U[i] - 1; ll v = V[i] - 1; rep(j, 5) { if (A[v] == 1) { if (j == 4) continue; G[u * 5 + j].push_back({v * 5 + j + 1, 1}); } else { G[u * 5 + j].push_back({v * 5 + 0, 1}); } } rep(j, 5) { if (A[u] == 1) { if (j == 4) continue; G[v * 5 + j].push_back({u * 5 + j + 1, 1}); } else { G[v * 5 + j].push_back({u * 5 + 0, 1}); } } } vector<ll> dis, prev; dijkstra(G, 0, dis, prev); ll ans = INF; rep(i, 5) { chmin(ans, dis[5 * (N - 1) + i]); } if (ans == INF) ans = -1; std::cout << ans << '\n'; return 0; } #else // #ifndef ONLINE_JUDGE // #define _GLIBCXX_DEBUG 1 //[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意 // #endif #ifdef ONLINE_JUDGE #define NDEBUG #include <atcoder/all> #endif #include <bits/stdc++.h> // # include <boost/multiprecision/cpp_dec_float.hpp> // # include <boost/multiprecision/cpp_int.hpp> // # include <boost/rational.hpp> // namespace mp = boost::multiprecision; // // 任意長整数型 // using Bint = mp::cpp_int; // // 仮数部が32桁(10進数)の浮動小数点数型 // using Real32 = mp::number<mp::cpp_dec_float<32>>; // // 仮数部が1024桁(10進数)の浮動小数点数型 // using Real1024 = mp::number<mp::cpp_dec_float<1024>>; // // ついでに有理数型 // using Rat = boost::rational<Bint>; using namespace atcoder; using namespace std; using ll = long long; using ld = long double; #define double ld ll INF = 2e18; using P = pair<ll, ll>; #define pb push_back #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define reprev(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--) #define reps(i, n) for (ll i = 1; i <= (ll)(n); i++) #define for_(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) #define all(v) v.begin(), v.end() template <typename T> inline bool chmin(T &a, const T &b) { bool c = a > b; if (c) a = b; return c; } template <typename T> inline bool chmax(T &a, const T &b) { bool c = a < b; if (c) a = b; return c; } template <typename T> inline T ceil(T a, T b) { return (a + (b - 1)) / b; } using mint = modint998244353; // using mint = modint1000000007; // using mint = static_modint<10>;//使うときはコメントアウトを外す template <typename T> using vc = vector<T>; template <class T> istream &operator>>(istream &i, vc<T> &v) { rep(j, (ll)size(v)) i >> v[j]; return i; } template <class T> ostream &operator<<(ostream &o, const vc<T> &v) { rep(j, (ll)size(v)) { if (j) o << " "; o << v[j]; } o << endl; return o; } #define INCLUDED_MAIN #include __FILE__ #endif