链接：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
输入例子:
4 4 1 3
1 2 8
1 3 65536
2 4 2
4 3 16
输出例子:
256
-->
示例1
输入
4 4 1 3
1 2 8
1 3 65536
2 4 2
4 3 16
输出
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 ;
}