Speed Up

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct A{
    int nextNode,weEdge;
};
vector<A> g[80800];
struct B{
    ll currNode,sumTime,drink,last,divisor;
    bool operator<(const B&o)const{
        return sumTime>o.sumTime;
    }
};
priority_queue<B> heap;
ll t[80800][12];
int markdrink[80800];
int main(){
    cin.tie(0) -> sync_with_stdio(0);
    int n,l,m,q,u,v,w;
    cin>>n>>m>>l>>q;
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    int mm;
    for(int i=0;i<l;i++){
        cin>>mm;
        markdrink[mm]=1;
    }
    for(int i=0;i<80800;i++)
        for(int j=0;j<12;j++)
            t[i][j] = 1e18;
    heap.push({1,0,0,-1,1});
    t[1][0]=0;
    ll mn=1e18;
    while(!heap.empty()){
        B now = heap.top();
        heap.pop();
        // printf("%lld %lld %lld\n",now.currNode,now.sumTime,now.drink);
        if(now.currNode==n){
            cout << now.sumTime << '\n';
            return 0;
        }
        for(auto x:g[now.currNode]){
            if(t[x.nextNode][now.drink] > now.sumTime + x.weEdge/now.divisor){
                t[x.nextNode][now.drink] = now.sumTime + x.weEdge/now.divisor;
                heap.push({x.nextNode,t[x.nextNode][now.drink],now.drink,now.last,now.divisor});
            }
            if(now.last != now.currNode && markdrink[now.currNode] && now.drink<q && t[x.nextNode][now.drink+1] > now.sumTime + (x.weEdge/(now.divisor*2))){
                t[x.nextNode][now.drink+1] = now.sumTime + (x.weEdge/(now.divisor*2));
                heap.push({x.nextNode,t[x.nextNode][now.drink+1],now.drink+1,now.currNode,now.divisor*2});
            }
        }
    }
    return 0;
}
/*
9 9 1 1
1 2 256
2 3 256
3 4 256
4 9 256
1 5 256
5 6 256
6 7 256
7 8 256
8 9 256
5

*/