图论一顿套模版__题解

这道题水

既然是2的整数次幂，所以先log一下

这题方法很多，我用的是Dijkstra+堆优化

直接最短路，天下人都会

上AC Code：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define L long long
int n,m,s,t,dis[50003],head[50003],cnt=0;
L log(L Z){
    L su=0;
    while(Z>1){
        Z>>=1;
        ++su;
    }
    return su;
}
L qpow(L a1,L b,L p){
    L ret=1;
    while(b){
        if(b%2==1) ret=ret*a1%p;
        a1=a1*a1%p;
        b/=2;
    }
    return ret;
}
int read(){
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
struct Edge{int v,w,nxt;} e[100003];
inline void add(int u,int v,int w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
struct node{
    int u,d;
    bool operator < (const node& rhs)const{return d>rhs.d;}
};
inline void Dijkstra() {
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<node> Q;
    Q.push((node){s,0});
    while(!Q.empty()){
        node fr=Q.top();
        Q.pop();
        int u=fr.u,d=fr.d;
        if(d!=dis[u]) continue;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                Q.push((node){v,dis[v]});
            }
        }
    }
}
int main(){
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++){
        L X=read(),Y=read(),Z=read();
        add(X,Y,log(Z));
    }
    Dijkstra();
    if(dis[t]>=dis[0]) return cout<<-1<<endl,0;
    cout<<qpow(2,dis[t],1000000007)<<endl;
return 0;
}

本题解到此结束！
PS：不点个赞再走？