“东信杯”广西大学第一届程序设计竞赛（同步赛）H 图论一顿套模版【最短路求对数技巧】

传送门：https://ac.nowcoder.com/acm/contest/283/H

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

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

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

由于答案可能很大，所以你需要将最后的答案对109+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的整数次幂。

输出描述:

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

若无解请输出 -1

示例1

输入

复制

输出

复制

题意概括：

求给定路径最小积。

解题思路：

当时优先队列优化的 Dijkstra 卡在了50%（精度问题）

赛后被佳欣哥一语点醒，求对数！！！！！！！

打比赛时就感觉好熟悉。。。

求对数，把乘法转换为加法（学过的思想，没A题，呵呵）

单源最短路 Dijksta SPFA随便搞了。

大数题慢慢打，注意每一个变量的精度（细节决定成败）。

AC code：

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <deque>
  5 #include <cstdio>
  6 #include <vector>
  7 #include <queue>
  8 #include <cmath>
  9 #define INF 0x3f3f3f3f
 10 #define LL long long
 11 using namespace std;
 12 
 13 const int MAXN = 5e4 + 50;
 14 const LL Mod = 1e9+7;
 15 typedef pair<LL, int> HeapNode; //精度
 16 struct edge
 17 {
 18     int v, nxt;
 19     LL w;           //精度
 20 }G[MAXN<<1];
 21 int head[MAXN];
 22 LL dis[MAXN];
 23 int N, M, cnt;
 24 
 25 inline void init()
 26 {
 27     for(int i = 0; i <= N; i++)
 28         head[i] = -1, dis[i] = INF;
 29     cnt = 0;
 30 }
 31 
 32 inline void add(int from, int to, LL we)
 33 {
 34     G[cnt].w = we;
 35     G[cnt].v = to;
 36     G[cnt].nxt = head[from];
 37     head[from] = cnt++;
 38 }
 39 
 40 void dij(int S)
 41 {
 42     priority_queue<HeapNode, vector<HeapNode>, greater<HeapNode> > heap;
 43     dis[S] = 0LL;
 44     heap.push(make_pair(0LL, S));   //精度
 45     while(!heap.empty())
 46     {
 47         pair<LL, int>T = heap.top();    //精度
 48         heap.pop();
 49 
 50         if(T.first != dis[T.second]) continue;
 51 
 52         for(int i = head[T.second]; i != -1; i = G[i].nxt)
 53         {
 54             int v = G[i].v;
 55             if(dis[v] > dis[T.second] + G[i].w)
 56             {
 57                 dis[v] = dis[T.second] + G[i].w;
 58                 heap.push(make_pair(dis[v], v));
 59 //                pre[v].no = T.second;
 60 //                pre[v].ed = i;
 61             }
 62         }
 63     }
 64 }
 65 
 66 LL qpow(LL x, LL n)
 67 {
 68     LL res = 1;
 69     while(n){
 70         if(n&1LL) res=(res*x)%Mod;  //精度
 71         x=(x*x)%Mod;
 72         n>>=1;
 73     }
 74     return res;
 75 }
 76 
 77 int main()
 78 {
 79     int a, b, S, T;
 80     LL c;
 81     while(~scanf("%d%d%d%d", &N, &M, &S, &T))
 82     {
 83         if(N == 0 && M == 0) break;
 84         init();
 85         while(M--)
 86         {
 87             scanf("%d%d%lld", &a, &b, &c);
 88             c = (LL)log2((double)c);       //求积转换为求和 //注意精度
 89             //printf("%lld
", c);
 90             add(a, b, c);
 91             //add(b, a, c);
 92         }
 93 
 94         dij(S);
 95         //printf("%lld
", dis[T]);
 96         if(dis[T] == INF) printf("-1
");
 97         else{
 98             LL ans = qpow(2LL, dis[T]);
 99             printf("%lld
", ans%Mod);
100         }
101     }
102 
103     return 0;
104 }

View Code