“东信杯”广西大学第一届程序设计竞赛（同步赛）H

链接：https://ac.nowcoder.com/acm/contest/283/H
来源：牛客网

题目描述

由于临近广西大学建校90周年校庆，西大开始了喜闻乐见的校园修缮工程！

然后问题出现了，西大内部有许许多多的道路，据统计有N栋楼和M条道路（单向），每条路都有“不整洁度”W，现在校方想知道从S楼到T楼的所有路径中，“不整洁度”乘积最小是多少。

由于答案可能很大，所以你需要将最后的答案对10⁹+7取模。

输入描述:

第一行为四个整数N、M、S、T，意义如上。

第2至第M+1行每行表示一条道路，有三个整数，分别表示每条道路的起点u，终点v和“不整洁度”W。

输入保证没有自环，可能有重边。

其中W一定是2的整数次幂。

输出描述:

输出一个整数，表示最小的不整洁度之乘积对10⁹+7取模的结果。

若无解请输出 -1

输入例子:

输出例子:

-->

示例1

输入

输出

256
解题思路：
由于每条路的权值可以转化成2的n次幂，所以权值的乘法可以转化成指数的加法，那么这道题就可以求权值指数和的最小值了，这道题就成最短路的问题了。
这里我用了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 0x3f3f3f3f

typedef long long ll;

const ll mod=1e9+;

const int maxn=+;

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,-);

    priority_queue<P,vector<P>,greater<P> > que;//使用优先队列

    que.push(P(,v));

    P tem;

    dis[v]=;

    while(!que.empty()){

        tem=que.top();

        que.pop();

        int i=tem.second;

        if(tem.first>dis[i])

        continue;

        for(int j=;j<sm[i].size();j++){

            edg e=sm[i][j];

            if(dis[e.to]==-||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=;

    edg tem;

    cin>>n>>m>>s>>t;

    for(int i=;i<m;i++){

        cin>>u>>v>>w;

        w=log(w)/log();

        tem.to=v;

        tem.w=w;

        sm[u].push_back(tem);

    }

    dij(s);

    if(dis[t]==-){

        cout<<"-1"<<endl;

    }

    else{

        ll tem=;

        while(dis[t]!=){

            if(dis[t]%==){

                ans=(ans*tem)%mod;

            }

            dis[t]/=;

            tem=(tem*tem)%mod;

        }

        cout<<ans<<endl;

    }

    return ;

}

秒客网