結果
| 問題 |
No.3263 違法な散歩道
|
| ユーザー |
 kino0402
|
| 提出日時 | 2025-09-06 13:32:06 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 373 ms / 2,000 ms |
| コード長 | 10,724 bytes |
| コンパイル時間 | 10,033 ms |
| コンパイル使用メモリ | 454,048 KB |
| 実行使用メモリ | 77,784 KB |
| 最終ジャッジ日時 | 2025-09-06 13:32:29 |
| 合計ジャッジ時間 | 16,464 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
コンパイルメッセージ
main.cpp:103:12: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
103 | void debug(auto A){rep(i,A.size())cerr<<A[i]<<" \n"[i==A.size()-1];}
| ^~~~
main.cpp:104:13: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
104 | void debug2(auto A){rep(i,A.size())debug(A[i]);}
| ^~~~
main.cpp:105:15: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
105 | void debugstr(auto A){rep(i,A.size())cerr<<A[i]<<" \n"[i==A.size()-1];}
| ^~~~
main.cpp:106:16: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
106 | void debugstr2(auto A){rep(i,A.size())debugstr(A[i]);}
| ^~~~
main.cpp:267:26: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
267 | vecll dijkstra(ll N,ll S,auto G){
| ^~~~
main.cpp:303:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
303 | void warshall_floyd(auto &dis){
| ^~~~
main.cpp:314:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
314 | vecll zahyouassyuku(auto X){
| ^~~~
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
#include<boost/multiprecision/cpp_dec_float.hpp>
#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace atcoder;
//-----=====macro=====-----
using ll = long long;
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define doubleketa(i) cout<<fixed<<setprecision(i);
#define speedup std::cin.tie(0)->sync_with_stdio(0);
#define _GLIBCXX_DEBUG //優先度付きキュー使って時間制限厳しい場合コメントアウト
#define int_max 2147483647
#define int_min -2147483647
#define uint_max 4294967295
#define ll_max 9223372036854775807
#define ll_min -9223372036854775807
#define ull_max 18446744073709551615
#define rep(i,n) for(ll i=0;i<(n);i++)
#define reps(i,n) for(ll i=1;i<=(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(n);i++)
#define all(a) (a).begin(), (a).end()
#define repc(i,n,A) rep(i,n)cin>>A[i]
#define REPC(i,j,n,A) REP(i,j,n)cin>>A[i]
#define repc2(i,n,A,B) rep(i,n)cin>>A[i]>>B[i]
#define REPC2(i,j,n,A,B) REP(i,j,n)cin>>A[i]>>B[i]
#define repc2vec(i,j,a,b,A) rep(i,a)rep(j,b)cin>>A[i][j]
#define REPC2VEC(i,j,k,a,b,A) REP(i,k,a)REP(j,k,b)cin>>A[i][j]
#define repair(i,n,A) rep(i,n)cin>>A[i].F>>A[i].S
#define REPAIR(i,j,n,A) REP(i,j,n)cin>>A[i].F>>A[i].S
#define ST(A) sort(all(A))
#define RV(A) reverse(all(A))
#define juufuku(A) A.erase(unique(all(A)),A.end());
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define Endl endl
#define F first
#define S second
#define yes(b) ((b)?"yes":"no")
#define Yes(b) ((b)?"Yes":"No")
#define YES(b) ((b)?"YES":"NO")
#define TA(b) ((b)?"Takahashi":"Aoki")
#define AB(b) ((b)?"Alice":"Bob")
using veci=vector<int>; using veci2=vector<veci>; using veci3=vector<veci2>;
using pi=pair<int,int>; using vecpi=vector<pi>; using vecpi2=vector<vecpi>;
using vecll=vector<ll>; using vecst=vector<string>; using vecch=vector<char>;
using vecll2=vector<vecll>; using vecst2=vector<vecst>; using pll=pair<ll,ll>;
using vecch2=vector<vecch>; using vecpll=vector<pll>; using vecpll2=vector<vecpll>;
using vecbo=vector<bool>; using vecbo2=vector<vecbo>;
using vecdo=vector<double>; using vecdo2=vector<vecdo>;
using pq=priority_queue<ll>; using pqp=priority_queue<pll>;
using pqg=priority_queue<ll,vecll,greater<ll>>;
using pqpg=priority_queue<pll,vecpll,greater<pll>>;
template <typename T> inline T _gcd(T a,T b){return (b==0)?a:_gcd(b,a%b);}//最大公約数
template <typename T> inline T _lcm(T a,T b){return (a*b)/_gcd(a,b);}//最小公倍数
template <typename T>
bool chmax(T &a,const T& b){
if(a<b){
a=b;
return true;
}
return false;
}
template <typename T>
bool chmin(T &a,const T& b){
if(a>b){
a=b; // aをbで更新
return true;
}
return false;
}
ll max(int a,ll b){return max((ll)a,b);}
ll max(ll a,int b){return max((ll)b,a);}
ll min(int a,ll b){return min((ll)a,b);}
ll min(ll a,int b){return min((ll)b,a);}
ll max3(ll a,ll b,ll c){return max(a,max(b,c));}
ll min3(ll a,ll b,ll c){return min(a,min(b,c));}
vecll DX={0,1,0,-1,1,1,-1,-1};
vecll DY={1,0,-1,0,1,-1,1,-1};
ll mod=998244353;
ll modgyakugen=499122177;
ll MOD=1000000007;
ll INF=1e18;
ll randint(ll a,ll b){return a+rand()%(b-a+1);}
double randouble(){return 1.0*rand()/RAND_MAX;}
void debug(auto A){rep(i,A.size())cerr<<A[i]<<" \n"[i==A.size()-1];}
void debug2(auto A){rep(i,A.size())debug(A[i]);}
void debugstr(auto A){rep(i,A.size())cerr<<A[i]<<" \n"[i==A.size()-1];}
void debugstr2(auto A){rep(i,A.size())debugstr(A[i]);}
//ACL 遅延セグ木
ll inf_seg=8e18,id_seg=8e18;
struct SegSum{
ll value;
ll size;
};
ll op_min(ll a,ll b){return min(a,b);}
ll op_max(ll a,ll b){return max(a,b);}
ll e_min(){return inf_seg;}
ll e_max(){return -inf_seg;}
ll m_add(ll a,ll b){return a+b;}
ll m_change(ll a,ll b){return (a==id_seg?b:a);}
ll c_add(ll a,ll b){return a+b;}
ll c_change(ll a,ll b){return (a==id_seg?b:a);}
ll id_add(){return 0;}
ll id_change(){return id_seg;}
SegSum op_sum(SegSum a,SegSum b){return {a.value+b.value,a.size+b.size};}
SegSum e_sum(){return {0,0};}
SegSum m_add_sum(ll a,SegSum b){return {b.value+a*b.size,b.size};}
SegSum m_change_sum(ll a,SegSum b){
if(a!=id_seg)b.value=a*b.size;
return b;
}
using seg_add_min=lazy_segtree<ll,op_min,e_min,ll,m_add,c_add,id_add>;
using seg_add_max=lazy_segtree<ll,op_max,e_max,ll,m_add,c_add,id_add>;
using seg_change_min=lazy_segtree<ll,op_min,e_min,ll,m_change,c_change,id_change>;
using seg_change_max=lazy_segtree<ll,op_max,e_max,ll,m_change,c_change,id_change>;
using seg_add_sum=lazy_segtree<SegSum,op_sum,e_sum,ll,m_add_sum,c_add,id_add>;
using seg_change_sum=lazy_segtree<SegSum,op_sum,e_sum,ll,m_change_sum,c_change,id_change>;
//-----=====library=====-----
//trie木
template<ll char_size,ll base>
struct Trie{
struct Node{ // 頂点を表す構造体
vecll next; // 子の頂点番号を格納。存在しなければ-1
vecll accept; // 末端がこの頂点になる単語の word_id を保存
ll c; // base からの間隔をll型で表現したもの
ll common; // いくつの単語がこの頂点を共有しているか
Node(ll c_):c(c_),common(0){
next.assign(char_size,-1);
}
};
vector<Node>nodes; // trie木本体
ll root;
Trie():root(0){
nodes.pb(Node(root));
}
//単語の挿入
void insert(const string &word,ll word_id){
ll node_id=0;
rep(i,word.size()){
ll c=(ll)(word[i]-base);
ll &next_id=nodes[node_id].next[c];
if(next_id==-1){// 次の頂点が存在しなければ追加
next_id=(ll)nodes.size();
nodes.pb(Node(c));
}
++nodes[node_id].common;
node_id = next_id;
}
++nodes[node_id].common;
nodes[node_id].accept.pb(word_id);
}
void insert(const string &word){
insert(word,nodes[0].common);
}
//単語とprefixの検索
bool search(const string &word,bool prefix=false){
ll node_id = 0;
rep(i,word.size()){
ll c=(ll)(word[i]-base);
ll &next_id=nodes[node_id].next[c];
if(next_id==-1){ // 次の頂点が存在しなければ終了
return false;
}
node_id = next_id;
}
return(prefix)?true:nodes[node_id].accept.size()>0;
}
//prefixを持つ単語が存在するかの検索
bool start_with(const string &prefix){
return search(prefix,true);
}
//挿入した単語の数
int count() const{
return(nodes[0].common);
}
//Trie木のノード数
int size() const{
return ((ll)nodes.size());
}
};
//二分探索
ll nibutan(ll K,vecll& V){
ll ng=-1;
ll ok=V.size();
while(ok-ng>1){
ll m=(ng+ok)/2;
if(V[m]>=K)ok=m;
else ng=m;
}
return ok;
}
//素因数分解
vecpll soinsuubunkai(ll N){
vecpll res;
for(ll a=2;a*a<=N;a++){
if(N%a!=0)continue;
int ex=0;//指数
//割れる限り割る
while(N%a==0){
ex++;
N/=a;
}
//結果をpb
res.pb({a,ex});
}
//後に残った数について
if(N!=1)res.pb({N,1});
return res;
//N=6 {2,1} {3,1}(2^1*3^1)のようになる autoで受け取ろう
}
//約数列挙
vecll yakusuurekkyo(ll N){
//答えを表す集合
vecll res;
//各整数iがNの約数かどうかを調べる
for (ll i=1;i*i<=N;++i){
//iがNの約数でない場合はスキップ
if(N%i!=0)continue;
//iは約数である
res.pb(i);
//N÷iも約数である(重複に注意)
if(N/i!=i)res.pb(N/i);
}
//約数をソートして出力
ST(res);
return res;
}
//桁数
ll ketasuu(ll num){
ll digit=0;
while(num!=0){
num/=10;
digit++;
}
return digit;
}
//ダイクストラ(頂点数,スタート,グラフ)
vecll dijkstra(ll N,ll S,auto G){
vecll dis(N,ll_max);
vecbo vis(N);
pqpg Q;
dis[S]=0;
Q.push(mp(0,S));
while(!Q.empty()){
ll pos=Q.top().S;Q.pop();
if(vis[pos]==true)continue;
vis[pos]=true;
rep(i,G[pos].size()){
ll nex=G[pos][i].F;
ll cost=G[pos][i].S;
if(dis[nex]>dis[pos]+cost){
dis[nex]=dis[pos]+cost;
Q.push(mp(dis[nex],nex));
}
}
}
return dis;
}
//エラトステネスの篩
vecbo furui(ll N) {
vecbo isprime(N+1,true);
isprime[1]=false;
for(ll p=2;p<=N;++p){
if(!isprime[p])continue;
for(ll q=p*2;q<=N;q+=p){
isprime[q]=false;
}
}
return isprime;
}
//ワーシャルフロイド
void warshall_floyd(auto &dis){
rep(k,dis.size()){
rep(i,dis.size()){
rep(j,dis.size()){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
}
//座標圧縮
vecll zahyouassyuku(auto X){
vecll x=X;
ST(x);
juufuku(x);
vecll ans(X.size());
rep(i,X.size())ans[i]=lower_bound(all(x),X[i])-x.begin();
return ans;
}
//BFS(グリッド)
vecll2 BFSgrid(vecst G,ll Sx,ll Sy,ll H,ll W){
vecll2 dis(H,vecll(W));
rep(i,H)rep(j,W)dis[i][j]=-1;
dis[Sx][Sy]=0;
queue<pll>Q;
Q.push(mp(Sx,Sy));
while(!Q.empty()){
ll x=Q.front().F,y=Q.front().S;
Q.pop();
rep(i,4){
ll nx=x+DX[i],ny=y+DY[i];
if(nx<0||nx>=H||ny<0||ny>=W)continue;
if(dis[nx][ny]!=-1)continue;
if(G[nx][ny]=='#')continue;
Q.push(mp(nx,ny));
dis[nx][ny]=dis[x][y]+1;
}
}
return dis;
}
//コンビネーション
//テーブルを作る前処理
void COMinit(ll C_max,vecll &fac,vecll &finv){
vecll inv(C_max);
fac[0]=fac[1]=1;
finv[0]=finv[1]=1;
inv[1]=1;
REP(i,2,C_max){
fac[i]=fac[i-1]*i%mod;
inv[i]=mod-inv[mod%i]*(mod/i)%mod;
finv[i]=finv[i-1]*inv[i]%mod;
}
}
//二項係数計算
ll COM(ll n,ll k,vecll &fac,vecll &finv){
if(n<k)return 0;
if(n<0||k<0)return 0;
return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
ll div_mod(ll a,ll b,ll m){
a=a%m;
return (a*inv_mod(b,m))%m;
}
//-----=====writing part=====-----
int main(){
ll n,m,k,t;
cin>>n>>m;
vecll x(m),y(m);
rep(i,m)cin>>x[i]>>y[i];
cin>>k;
vecll iw(n);
rep(i,k){
cin>>t;
iw[t-1]=1;
}
vecpll2 g(n*5);
rep(i,m){
if(iw[y[i]-1]==0){
rep(j,5)g[(x[i]-1)*5+j].eb(mp((y[i]-1)*5,1));
}else{
rep(j,4)g[(x[i]-1)*5+j].eb(mp((y[i]-1)*5+j+1,1));
}
if(iw[x[i]-1]==0){
rep(j,5)g[(y[i]-1)*5+j].eb(mp((x[i]-1)*5,1));
}else{
rep(j,4)g[(y[i]-1)*5+j].eb(mp((x[i]-1)*5+j+1,1));
}
}
auto dis=dijkstra(n*5,0,g);
ll ans=INF;
rep(i,5)chmin(ans,dis[(n-1)*5+i]);
cout<<(ans==INF?-1:ans);
//cout<<dis[n*5-1];
/*rep(i,n){
rep(j,5)cout<<min(dis[i*5+j],100)<<" ";
cout<<endl;
}*/
}