2019 Shaanxi Provincial race K-variant Dijstra

Preface ：

A class with certain restrictions Dijstra Find the shortest question type

The main idea of the topic :

Single starting point , The shortest path with multiple endpoints .
Every node to , There will be $d_i$ A monster comes out and will $d_i$ link $i$ The edge of the point is blocked . Their goal is to maximize your shortest path . Ask you the shortest result

Topic ideas :

practice :
Will end $d_i=0$. Then run from the finish line Dijstra, Take it out of the queue every time $v$, if $d_v>0$, Make $d_v--$, continue .
otherwise : Update this point $dist$

correctness :
1. Why start from the end , Because it stopped after the end , Don't consider this point $d_i$ 了 .
Even if the end $d=1e9$ It's useless ？

2. Think that every time you take it out of the queue, it must be the best one in the current situation .$d_i--$ It means that we must use $i$ A monster of to block this side .

Complexity :
The upper bound of relaxation times is the number of edges . So complexity :$O(mlogm)$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int a[maxn];
template <typename T>
void read(T & x){
     x = 0;T f = 1;char ch = getchar();while(!isdigit(ch)){
    if(ch == '-') f = -1;
ch = getchar();}while (isdigit(ch)){
    x = x * 10 + (ch ^ 48);ch = getchar();}x *= f;}
template <typename T>
void write(T x){
    if(x < 0){
    putchar('-');x = -x;}if (x > 9)write(x / 10);putchar(x % 10 + '0');}
struct Node{
    
    int id , v;
    bool operator < (const Node & a) const
    {
    
        return v > a.v;
    }
};
priority_queue<Node> q;
vector<pii> e[maxn];
int dist[maxn] , d[maxn] , bk[maxn];
void init (int n){
    
    for (int i = 1 ; i <= n ; i++){
    
        e[i].clear();
        dist[i] = -1;
        bk[i] = d[i] = 0;
    }
}
int main()
{
    
    int t;  read(t);
    while (t--){
    
        int n , m , k; read(n);read(m);read(k);
        init (n);
        vi st;
        for (int i = 1 ; i <= k ; i++){
    
            int x; read(x);
            st.push_back(x);
        }
        for (int i = 1 ; i <= n ; i++) read(d[i]);
        for (int i = 1 ; i <= m ; i++){
    
            int x , y , z;
            read(x);
            read(y);
            read(z);
            e[x].push_back({
    y , z});
            e[y].push_back({
    x , z});
        }
        for (auto & g : st){
    
            d[g] = 0;
            dist[g] = 0;
            q.push({
    g , 0});
        }
        while (q.size()){
    
            Node u = q.top();
            int id = u.id , dd = u.v;
            q.pop();
            //cout << " Now in " << id << " also " << d[id] << " Time  " << dd << endl;
            if (d[id]){
    
                d[id] = max(d[id] - 1 , 0);
                continue;
            }
            if (bk[id]) continue;
            bk[id] = 1;
            dist[id] = dd;
            //cout << " Will succeed dist" << id << " Assigned as " << dist[id] << endl;
            for (auto & g : e[id]){
    
                int v = g.first , w = g.second;
                if (dist[v] == -1 || dist[v] > dd + w)
                    q.push({
    v , dd + w});
            }
        }
        printf("%d\n" , dist[1]);
    }
    return 0;
}