Dijkstra的优先队列

模板

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 2147483647
typedef long long ll;
const ll mod=1e9+7;
const int maxn=50000+50;
ll dis[maxn];
struct edg{
    int to;
    int w;
};
vector<edg > sm[maxn];
typedef pair<int ,int > P;//最短距离，标点
void dij(int v){
    fill(dis,dis+maxn,-1);
    priority_queue<P,vector<P>,greater<P> > que;
    que.push(P(0,v));
    P tem;
    dis[v]=0;
    while(!que.empty()){
        tem=que.top();
        que.pop();
        int i=tem.second;
        if(tem.first>dis[i])
        continue;
        for(int j=0;j<sm[i].size();j++){
            edg e=sm[i][j];
            if(dis[e.to]==-1||dis[e.to]>dis[i]+e.w){
                dis[e.to]=dis[i]+e.w;
                que.push(P(dis[e.to],e.to));
            }
        }
    }
}
int main(){
    int n,m,s,t;
    int u,v;
    ll w;
    ll ans=1;
    edg tem;
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        w=log(w)/log(2);
        tem.to=v;
        tem.w=w;
        sm[u].push_back(tem);
    }
    dij(s);
    if(dis[t]==-1){
        cout<<"-1"<<endl;
    }
    else{
            //cout<<dis[t]<<endl;
        ll tem=2;
        while(dis[t]!=0){
            if(dis[t]%2==1){
                ans=(ans*tem)%mod;
            }
            dis[t]/=2;
            tem=(tem*tem)%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}