E. Rendez-vous de Marian et Robin
分层图图论问题：
代码：
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(v) v.begin(),v.end()
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f;
const int N = 4e5+5;
int n,m,k;
struct node{int x,w,id;bool operator<(const node &u)const{return w==u.w?x>u.x:w>u.w;}
};
vector<node>g[N];
int st[N];//horse
int d[N][2],dd[N][2];
int ok[N][2];void dijkstra(){priority_queue<node>pq;for(int i=1;i<=n;i++){d[i][0] = d[i][1] = inf;}pq.push({1LL,d[1][st[1]] = 0,st[1]});while(!pq.empty()){int x = pq.top().x;int w = pq.top().w;int op = pq.top().id;pq.pop();if(ok[x][op])continue;ok[x][op] = 1;for(const auto &[y,ww,opp]:g[x]){if(op){if(d[y][1]>d[x][1]+ww/2LL){d[y][1] = d[x][1] + ww/2LL;pq.push({y,d[y][1],1LL});}}else if(st[y]){if(d[y][1]>d[x][0] + ww){d[y][1] = d[x][0] + ww;pq.push({y,d[y][1],1LL});}}else{if(d[y][0]>d[x][0]+ww){d[y][0] = d[x][0] + ww;pq.push({y,d[y][0],0LL});}}}}return;}void dijkstra1(){priority_queue<node>pq;for(int i=1;i<=n;i++){dd[i][0] = dd[i][1] = inf;}pq.push({n,dd[n][st[n]] = 0,st[n]});while(!pq.empty()){int x = pq.top().x;int w = pq.top().w;int op = pq.top().id;pq.pop();if(ok[x][op])continue;ok[x][op] = 1;for(const auto &[y,ww,opp]:g[x]){if(op){if(dd[y][1]>dd[x][1]+ww/2LL){dd[y][1] = dd[x][1] + ww/2LL;pq.push({y,dd[y][1],1LL});}}else if(st[y]){if(dd[y][1]>dd[x][0] + ww){dd[y][1] = dd[x][0] + ww;pq.push({y,dd[y][1],1LL});}}else{if(dd[y][0]>dd[x][0]+ww){dd[y][0] = dd[x][0] + ww;pq.push({y,dd[y][0],0LL});}}}}return;}void solve(){cin>>n>>m>>k;for(int i=1;i<=n;i++){g[i].clear();st[i] = 0;}for(int i=1;i<=k;i++){int x;cin>>x;st[x] = 1;}for(int i=1;i<=n;i++){ok[i][0] = ok[i][1] = 0;}for(int i=1;i<=m;i++){int x,y,w;cin>>x>>y>>w;g[x].push_back({y,w});g[y].push_back({x,w});}dijkstra();for(int i=1;i<=n;i++){ok[i][0] = ok[i][1] = 0;}dijkstra1();int ans = inf;for(int i=1;i<=n;i++){int res = max(min(d[i][0],d[i][1]),min(dd[i][0],dd[i][1]));ans = min(ans,res);}if(ans>=inf/2LL){cout<<-1<<"\n";return;}else{cout<<ans<<"\n";return;}}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T = 1;cin>>T;while(T--){solve();}return 0;
}