图论一顿套模版

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。

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

$1\le N\le 50000$

$1 \leq M \leq 100000$

$1 \leq U, V \leq N$

$1 \leq W \leq 10^{10}$

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

输出描述:

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

若无解请输出 -1

示例1

输入

输出

因为W是2的整数次幂，所以可以把W=log2(W),由乘法变成加法

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<string>
  6 #include<cmath>
  7 #include<vector>
  8 #include<queue>
  9 #define maxn 200005
 10 #define INF 0x3f3f3f3f3f3f3f3f
 11 const long long MOD=1e9+7;
 12 using namespace std;
 13  
 14 int n,m,k;
 15 struct sair{
 16     long long len,pos;
 17     friend bool operator<(sair a,sair b){
 18         return a.len>b.len;
 19     }
 20 };
 21 long long dis[maxn];
 22 long long vis[maxn];
 23  
 24 long long pow_mod(long long sum){
 25     long long ans=1;
 26     long long b=2;
 27     while(sum){
 28         if(sum&1) ans=(b*ans)%MOD;
 29         b=(b*b)%MOD;
 30         sum>>=1;
 31     }
 32     return ans;
 33 }
 34  
 35 vector<pair<long long,long long> >v[maxn];
 36 void Dijstra(int s,int t){
 37     priority_queue<sair>q;
 38     sair tmp;
 39     tmp.len=0,tmp.pos=s;
 40     dis[s]=0;
 41     q.push(tmp);
 42     while(!q.empty()){
 43         tmp=q.top();
 44         q.pop();
 45         long long pos=tmp.pos;
 46         if(vis[pos]){
 47             continue;
 48         }
 49         vis[pos]=1;
 50         for(int i=0;i<v[pos].size();i++){
 51             long long f=v[pos][i].first;
 52             long long len=v[pos][i].second;
 53  
 54             if(dis[f]>dis[pos]+len){
 55                 dis[f]=dis[pos]+len;
 56                 tmp.pos=f;
 57                 tmp.len=dis[f];
 58                 q.push(tmp);
 59             }
 60         }
 61     }
 62  
 63     if(dis[t]==INF) cout<<-1<<endl;
 64     else cout<<pow_mod(dis[t])<<endl;
 65 }
 66  
 67  
 68  
 69 int main(){
 70  
 71     std::ios::sync_with_stdio(false);
 72     int s,t;
 73     cin>>n>>m>>s>>t;
 74     for(int i=0;i<=n;i++){
 75         dis[i]=INF;
 76         vis[i]=0;
 77     }
 78     for(int i=0;i<=n;i++){
 79         v[i].clear();
 80     }
 81     int a,b;
 82     long long c;
 83     int j;
 84     for(int i=1;i<=m;i++){
 85         cin>>a>>b>>c;
 86         c=log2(c);
 87         for(j=0;j<v[a].size();j++){
 88             if(v[a][j].first==b){
 89                 if(v[a][j].second>c){
 90                     v[a][j].second=c;
 91                 }
 92                 break;
 93             }
 94         }
 95         if(j==v[a].size()){
 96             v[a].push_back(make_pair(b,c));
 97         }
 98     }
 99     Dijstra(s,t);
100     system("pause");
101 }

View Code