IPST59: Speed Up

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

typedef long long lli;
typedef pair<int, int> pii;
typedef pair<lli, int> pli;
typedef pair<int, lli> pil;
typedef tuple<lli, int, int, int> tpp;

const int N = 8e4 + 5;
const int L = 10 + 5;
const int Q = 8 + 5;

vector<pii> adj[N];
vector<pil> cAdj[L];
vector<int> potion;
lli dist[L][N], cDist[L][Q][L];
int nVertex;
bool visited[N], cVisited[L][Q][L], isInCp[N];

void Dijkstra(int i){
    int st = potion[i];
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    for(int u = 0; u <= nVertex + 1; ++u){
        visited[u] = false;
    }
    dist[i][st] = 0;
    pq.emplace(dist[i][st], st);
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(visited[u]){
            continue;
        }
        if(isInCp[u]){
            int idx = lower_bound(potion.begin(), potion.end(), u) - potion.begin();
            if(i != idx){
                cAdj[i].emplace_back(idx, dist[i][u]);
            }
        }
        visited[u] = true;
        for(pii nxt : adj[u]){
            int v = nxt.first;
            int w = nxt.second;
            if(!visited[v] && dist[i][u] + w < dist[i][v]){
                dist[i][v] = dist[i][u] + w;
                pq.emplace(dist[i][v], v);
            }
        }
    }
}

int main(){

    int nEdge, nPotionRoom, limPotion;
    scanf("%d%d%d%d", &nVertex, &nEdge, &nPotionRoom, &limPotion);
    for(int i = 1; i <= nEdge; ++i){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].emplace_back(v, w);
    }
    adj[0].emplace_back(1, 0);
    adj[nVertex].emplace_back(nVertex + 1, 0);

    potion.push_back(0);
    potion.push_back(nVertex + 1);
    for(int i = 1; i <= nPotionRoom; ++i){
        int u;
        scanf("%d", &u);
        potion.push_back(u);
        isInCp[u] = true;
    }
    isInCp[nVertex + 1] = true;
    sort(potion.begin(), potion.end());

    for(int i = 0; i <= nPotionRoom; ++i){
        for(int u = 0; u <= nVertex + 1; ++u){
            dist[i][u] = 1e18;
        }
    }
    for(int i = 0; i <= nPotionRoom; ++i){
        Dijkstra(i);
    }

    for(int u = 0; u <= nPotionRoom + 1; ++u){
        for(int ptn = 0; ptn <= limPotion; ++ptn){
            for(int lst = 0; lst <= nPotionRoom + 1; ++lst){
                cDist[u][ptn][lst] = 1e18;
            }
        }
    }
    priority_queue<tpp, vector<tpp>, greater<tpp>> pq;
    cDist[0][0][0] = 0;
    pq.emplace(cDist[0][0][0], 0, 0, 0);
    while(!pq.empty()){
        int u = get<1>(pq.top());
        int ptn = get<2>(pq.top());
        int lst = get<3>(pq.top());
        pq.pop();
        if(cVisited[u][ptn][lst]){
            continue;
        }
        if(u == nPotionRoom + 1){
            cout << cDist[u][ptn][lst];
            return 0;
        }
        cVisited[u][ptn][lst] = true;
        if(u != lst && ptn < limPotion){
            if(!cVisited[u][ptn + 1][u] && cDist[u][ptn][lst] < cDist[u][ptn + 1][u]){
                cDist[u][ptn + 1][u] = cDist[u][ptn][lst];
                pq.emplace(cDist[u][ptn + 1][u], u, ptn + 1, u);
            }
        }
        for(pil nxt : cAdj[u]){
            int v = nxt.first;
            lli w = nxt.second;
            if(!cVisited[v][ptn][lst] && cDist[u][ptn][lst] + (w >> ptn) < cDist[v][ptn][lst]){
                cDist[v][ptn][lst] = cDist[u][ptn][lst] + (w >> ptn);
                pq.emplace(cDist[v][ptn][lst], v, ptn, lst);
            }
        }
    }

    return 0;
}