#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=sta;i--) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; templatebool chmax(T &a, const T &b) {if(abool chmin(T &a, const T &b) {if(b struct Dijkstra{ struct Edge{ int to; T cost; Edge(int to,T cost):to(to),cost(cost){} bool operator<(const Edge &o)const{return cost>o.cost;} }; const T inf = (numeric_limits::max())/2;//infを設定する vector> G; vector ds; vector bs; Dijkstra(int n):G(n){} void add_edge(int u,int v,T c){ G[u].push_back(Edge(v,c)); } void build(vector &ss){ int n=G.size(); ds.assign(n,inf); bs.assign(n,-1); priority_queue pq; for(int s:ss) { ds[s]=0; pq.emplace(s,ds[s]); } while(!pq.empty()){ auto p=pq.top();pq.pop(); int v=p.to; if(ds[v]ds[v]+e.cost){ ds[e.to]=ds[v]+e.cost; bs[e.to]=v; pq.emplace(e.to,ds[e.to]); } } } } void build(int s){ vector v={s}; build(v); } T operator[](int k){return ds[k];} vector restore(int to){ vector res; if(bs[to]<0) return res; while(~to) res.emplace_back(to),to=bs[to]; reverse(res.begin(),res.end()); return res; } }; int n,m,k; int a[20010],b[20010];ll c[20010]; int r[20]; vector> D; ll dp[10010][10010]; void solve(){ cin >> n >> m >> k; Dijkstra dij(n); rep(i,k) { cin >> r[i]; r[i]--; } rep(i,m){ cin >> a[i] >> b[i] >> c[i];a[i]--;b[i]--; dij.add_edge(a[i],b[i],c[i]); dij.add_edge(b[i],a[i],c[i]); } D.resize(n); dij.build(0);D[0]=dij.ds; dij.build(n-1);D[n-1]=dij.ds; rep(i,k){ //cout << i << endl; if(D[a[r[i]]].size()