// https://qiita.com/Raclamusi/items/660f0f42c57e4371ed78 #ifdef INCLUDED_MAIN struct Edge { ll to; ll cost; }; using Graph = vector>; using P = pair; // const ll INF = 1LL << 60; /* dijkstra(G,s,dis,prev) 入力:グラフ G, 開始点 s, 距離を格納する dis, 最短経路の前の点を記録するprev 計算量:O(|E|log|V|) 副作用:dis, prevが書き換えられる 使用法 ``` //初期化は自動でされる vector dis, prev; dijkstra(G, r, dis, prev); ``` */ void dijkstra(const Graph &G, ll s, vector &dis, vector &prev) { ll N = G.size(); dis.resize(N, INF); prev.resize(N, -1); // 初期化 priority_queue, greater

> 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 get_path(const vector &prev, ll t) { vector 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 U(M), V(M); rep(i, M) { std::cin >> U[i] >> V[i]; } ll K; cin >> K; vc A(N, 0); rep(i, K) { ll a; cin >> a; a--; A[a]++; } vc> 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 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 #endif #include // # include // # include // # include // namespace mp = boost::multiprecision; // // 任意長整数型 // using Bint = mp::cpp_int; // // 仮数部が32桁(10進数)の浮動小数点数型 // using Real32 = mp::number>; // // 仮数部が1024桁(10進数)の浮動小数点数型 // using Real1024 = mp::number>; // // ついでに有理数型 // using Rat = boost::rational; using namespace atcoder; using namespace std; using ll = long long; using ld = long double; #define double ld ll INF = 2e18; using P = pair; #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 inline bool chmin(T &a, const T &b) { bool c = a > b; if (c) a = b; return c; } template inline bool chmax(T &a, const T &b) { bool c = a < b; if (c) a = b; return c; } template inline T ceil(T a, T b) { return (a + (b - 1)) / b; } using mint = modint998244353; // using mint = modint1000000007; // using mint = static_modint<10>;//使うときはコメントアウトを外す template using vc = vector; template istream &operator>>(istream &i, vc &v) { rep(j, (ll)size(v)) i >> v[j]; return i; } template ostream &operator<<(ostream &o, const vc &v) { rep(j, (ll)size(v)) { if (j) o << " "; o << v[j]; } o << endl; return o; } #define INCLUDED_MAIN #include __FILE__ #endif