E

https://codeforces.com/contest/2014/problem/E

In the humble act of meeting, joy doth unfold like a flower in bloom.

Absence makes the heart grow fonder. Marian sold her last ware at the Market at the same time Robin finished training at the Major Oak. They couldn’t wait to meet, so they both start without delay.

The travel network is represented as $n$ vertices numbered from $1$ to $n$ and $m$ edges. The $i$-th edge connects vertices $u_i$ and $v_i$, and takes $w_i$ seconds to travel (all $w_i$ are even). Marian starts at vertex $1$ (Market) and Robin starts at vertex $n$ (Major Oak).

In addition, $h$ of the $n$ vertices each has a single horse available. Both Marian and Robin are capable riders, and could mount horses in no time (i.e. in $0$ seconds). Travel times are halved when riding. Once mounted, a horse lasts the remainder of the travel. Meeting must take place on a vertex (i.e. not on an edge). Either could choose to wait on any vertex.

Output the earliest time Robin and Marian can meet. If vertices $1$ and $n$ are disconnected, output $-1$ as the meeting is cancelled.

既然他们要在一个点相聚，那么合理猜测答案是不是就是各自起点到该点的最短路取max。然后再所有相聚点中取min。

那么接下来考虑求他们的最短路，由于有骑马这个问题，所以dijk应该要多加一维状态描述是否骑马。此外，该点有没有马影响不到起点到该点的路径，所以状态表示为：$dist[u][0/1]$，表示从起点到u点，且刚到达u点时是否骑马的最短路。(ps.有马我们肯定是必骑的，那可能会导致：到某点且没马的状态没有处理到。不过实际上这个不影响结果，因为这个状态我们肯定用不到)。

那么就是个多维的dijk。需要注意的点：

• 多维状态直接定义一个新结构体，比你那什么array[HTML_REMOVED]方便多了。
• 要重载大于号，因为小根堆优先队列里面我们采用大于号比较。ps.默认的大根堆采用小于号比较。排序的规则与sort相反
• 优先队列默认是大根堆，要修改成小根堆
• st判重数组是必需的，开的和dist长得一样就好了。

语法补充

priority_queue<int, vector<int>, greater<int> > que;

其中，priority_queue 后的尖括号中：

• int 表示数据类型；
• vector<int> 表示数据的存储方式，在这里是使用 vector 存储（据说这样写上会快一些，不过我这里主要还是为了占一个位置，方便写第三个参数）；
• greater<int> 表示比较规则，这个 greater<int> 对应的比较规则就是 >（大于号），即 “我比你大，我把你推到顶上去”。

写的时候发现模板遗忘严重，贴出代码如下：

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
int n,m,h;

struct node{
    ll dist;int ver;bool curh;
    bool operator > (const node &t)const{
        return dist>t.dist;
    }
};

void dijkstra(int s,vector<vector<ll>> &d,vector<vector<pair<int,ll>>> &g,vector<bool> hs){
    d[s][0] = 0;
    vector<vector<bool>> st(n,vector<bool>(2,false));
    priority_queue<node,vector<node>,greater<node>> pq;
    pq.push({0,s,0});
    while(pq.size()){
        auto t =pq.top();
        pq.pop();
        if(st[t.ver][t.curh]) continue;
        st[t.ver][t.curh] = true;

        bool horse = t.curh || hs[t.ver];
        for(auto to:g[t.ver]){
            int u = to.first;ll w = horse?to.second/2:to.second;
            if(d[u][horse]> d[t.ver][t.curh]+w){
                d[u][horse] = d[t.ver][t.curh]+w;
                pq.push({d[u][horse],u,horse});
            }
        }
    }
}

void solve(){
    cin>>n>>m>>h;
    vector<bool> hs(n,0);
    vector<vector<pair<int,ll>>> g(n);
    for(int i=0;i<h;i++) {
        int c;cin>>c;hs[--c] = true;
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a--,b--; g[a].push_back({b,c});g[b].push_back({a,c});
    }
    vector<vector<ll>> dist1(n,vector<ll>(2,1e18));
    vector<vector<ll>> dist2(n,vector<ll>(2,1e18));
    dijkstra(0,dist1,g,hs);
    dijkstra(n-1,dist2,g,hs);

    ll ans = 1e18;
    for(int i=0;i<n;i++){
        ll x = max(min(dist1[i][0],dist1[i][1]),min(dist2[i][0],dist2[i][1]));
        ans = min(ans,x);
    }
    cout<<(ans>=1e17? -1ll:ans)<<endl;
}
int main(){     
    //delete when submit!!!!!!
    //freopen("in.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    int T=1;
    cin>>T;
    while(T--){
        solve();
    } 

    return 0;
}