[Nowcoder283H] 图论一顿套模版 (最短路)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://ac.nowcoder.com/acm/contest/283/H

有N栋楼和M条道路（单向），每条路都有“不整洁度”W，现在校方想知道从S楼到T楼的所有路径中，“不整洁度”乘积最小是多少。 由于答案可能很大，所以你需要将最后的答案对10E9+7取模。

因为权值会很大，所以直接拿乘积算最短路是不可以的，因为取模后数值大小无法比较。

需要注意的是，题目保证每一个权都是2的幂，虽然我没注意。。

于是我维护了权值的每一位，计算的时候只管它们最终都是2的多少次幂。

于是可以堆优化最短路，在堆里维护2的幂次，这样就能保证一个大小顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
typedef pair<LL, LL> PLL;
typedef struct Edge {
  LL v, w, next;
}Edge;
const LL mod = 1E9+7;
const LL maxn = 50050;
const LL maxm = 200100;
const LL inf = 1E18;
LL n, m, ee, s, t;
LL d[maxn][64];
LL head[maxn];
Edge e[maxm];

priority_queue<PLL, vector<PLL>, greater<PLL> > pq;

LL mul(LL x, LL n) {
  LL ret = 1;
  for(; n; x=(x*x)%mod,n>>=1) {
    if(n & 1) ret = (ret * x) % mod;
  }
  return ret;
}

void init() {
  ee = 0;
  memset(head, -1, sizeof(head));
}
void adde(LL u, LL v, LL w) {
  e[ee].v = v; e[ee].w = w; e[ee].next = head[u]; head[u] = ee++;
  // e[ee].v = u; e[ee].w = w; e[ee].next = head[v]; head[v] = ee++;
}

bool check(LL v, LL u, LL w=1) {
  LL a = 0, b = ceil(log(w)/log(2));
  for(LL i = 0; i < 64; i++) {
    a += d[v][i] * i;
    b += d[u][i] * i;
  }
  return a > b;
}

LL get(LL u) {
  LL a = 0;
  for(LL i = 0; i < 64; i++) {
    a += d[u][i] * i;
  }
  return a;
}

inline bool scan_d(LL &num) {
  char in;bool IsN=false;
  in=getchar();
  if(in==EOF) return false;
  while(in!='-'&&(in<'0'||in>'9')) in=getchar();
  if(in=='-'){ IsN=true;num=0;}
  else num=in-'0';
  while(in=getchar(),in>='0'&&in<='9'){
    num*=10,num+=in-'0';
  }
  if(IsN) num=-num;
  return true;
}

signed main() {
  // freopen("in", "r", stdin);
  LL u, v;
  LL w;
  while(scan_d(n)) {
    scan_d(m);
    scan_d(s);
    scan_d(t);
    init();
    for(LL i = 1; i <= n; i++) {
      for(int j = 0; j < 64; j++) d[i][j] = inf;
    }
    for(LL i = 0; i < m; i++) {
      scan_d(u);
      scan_d(v);
      scan_d(w);
      adde(u, v, w);
    }
    for(int j = 0; j < 64; j++) {
      d[s][j] = 0;
    }
    pq.push(PLL(get(s), s));
    while(!pq.empty()) {
      PLL tmp = pq.top(); pq.pop();
      LL pw = tmp.first, u = tmp.second;
      if(get(u) < pw) continue;
      for(LL i = head[u]; ~i; i=e[i].next) {
        LL v = e[i].v; LL w = e[i].w;
        if(check(v, u, w)) {
          for(int j = 0; j < 64; j++) {
            d[v][j] = d[u][j];
          }
          int cur = ceil(log(w)/log(2));
          d[v][cur]++;
          pq.push(PLL(get(v), v));
        }
      }
    }
    if(d[t][0] == inf) {
      printf("-1\n");
      continue;
    }
    LL ret = 1;
    for(int i = 0; i < 64; i++) {
      if(d[t][i]) {
        ret *= mul(2LL,(i*d[t][i])%mod) % mod;
        ret %= mod;
      }
    }
    printf("%lld\n", ret);
  }
  return 0;
}