o59_oct_c2_speedup

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli INF = 1e18;
const int N = 8e4;
const int M = 2e5;
const int L = 10;
const int Q = 8;
using pi = pair <int, int>;
using pil = pair <int, lli>;
using pli = pair <lli, int>;
using plii = pair <lli, pi>;

vector <pil> g[N+10];
int n, m, l, q;
lli p[Q+10];

int Room[L+10];
bool isRoom[N+10];
lli dis_rr[L+10][L+10], dis_rn[L+10][N+10];
int vs_rn[L+10][N+10];

lli dis[N+10][Q+10];
bool vs[N+10][Q+10];

void Setting(){
    // ???
    for(int i=1;i<=l;i++){
        for(int j=1;j<=l;j++){
            dis_rr[i][j] = INF;
        }
    }
    for(int i=1;i<=l;i++){
        for(int j=1;j<=n;j++){
            dis_rn[i][j] = INF;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=8;j++){
            dis[i][j] = INF;
        }
    }
}

int BS(int u){
    int s = 1, e = l;
    while(s <= e){
        int mid = (s + e) / 2;
        if(Room[mid] == u) return mid;
        else if(Room[mid] > u) e = mid - 1;
        else s = mid + 1;
    }
}

int main(){

    p[0] = 1;
    for(int i=1;i<=Q;i++){
        p[i] = (lli) p[i-1] * 2;
    }

    scanf("%d%d%d%d", &n, &m, &l, &q);

    for(int i=1;i<=m;i++){
        int u, v;
        lli w;
        scanf("%d%d%lld", &u, &v, &w);
        g[u].push_back({v, w});
    }

    for(int i=1;i<=l;i++){
        scanf("%d", &Room[i]);
        isRoom[ Room[i] ] = true;
    }

    sort(Room+1, Room+l+1);

    Setting();

    for(int i=1;i<=l;i++){
        priority_queue <pli, vector <pli>, greater <pli>> pq;
        dis_rn[i][ Room[i] ] = 0;
        dis_rr[i][i] = 0;
        pq.push({ dis_rn[i][ Room[i] ] , Room[i] });
        while(!pq.empty()){
            lli d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            if(vs_rn[i][u]) continue;
            vs_rn[i][u] = true;
            if(isRoom[u])
                dis_rr[i][BS(u)] = d;
            for(auto vw: g[u]){
                int v = vw.first;
                lli w = vw.second;
                if(!vs_rn[i][v] and (lli) d + w < dis_rn[i][v]){
                    dis_rn[i][v] = (lli) d + w;
                    pq.push({ dis_rn[i][v] , v });
                }
            }
        }
    }

    priority_queue <plii, vector <plii>, greater <plii>> pq;
    if(isRoom[1] and q > 0){
        dis[1][1] = 0;
        pq.push({ dis[1][1] , {1, 1} });
    }
    else {
        dis[1][0] = 0;
        pq.push({ dis[1][0] , {1, 0} });
    }
    while(!pq.empty()){
        lli d = pq.top().first;
        int u = pq.top().second.first;
        int k = pq.top().second.second;
        pq.pop();
        if(vs[u][k]) continue;
        vs[u][k] = true;

        // printf("u %d d %lld k %d\n", u, d, k);

        if(u == n){
            printf("%lld", d);
            return 0;
        }

        if(isRoom[u]){
            int ui = BS(u);
            /// u -> n
            if(!vs[n][k] and (lli) d + (lli)dis_rn[ui][n]/p[k] < dis[n][k]){
                dis[n][k] = (lli) d + (lli)dis_rn[ui][n]/p[k];
                pq.push({ dis[n][k] , {n, k} });
            }
            /// room -> room -> ...
            if(k + 1 <= q){
                for(int i=1;i<=l;i++){
                    int v = Room[i];
                    if(ui == i) continue;
                    if(k + 1 <= q and !vs[v][k+1] and (lli) d + (lli)dis_rr[ui][i]/p[k] < dis[v][k+1]){
                        dis[v][k+1] = (lli) d + (lli)dis_rr[ui][i]/p[k];
                        pq.push({ dis[v][k+1], {v, k+1} });
                    }
                }
            }

        }
        else {
            for(auto vw: g[u]){
                int v = vw.first;
                lli w = vw.second;
                if(!isRoom[v] and !vs[v][k] and (lli) d + (lli)w/p[k] < dis[v][k]){
                    dis[v][k] = (lli) d + (lli)w/p[k];
                    pq.push({ dis[v][k] , {v, k} });
                }
                else if(isRoom[v] and k + 1 <= q and !vs[v][k+1] and (lli) d + (lli)w/p[k] < dis[v][k+1]){
                    dis[v][k+1] = (lli) d + (lli)w/p[k];
                    pq.push({ dis[v][k+1] , {v, k+1} });
                }
            }
        }
    }

    return 0;
}

/*

4 4 1 2
1 2 256
2 4 2560
2 3 256
3 2 256
3
1920

4 4 1 0
1 2 256
2 4 2560
2 3 256
3 2 256
1

*/