Tieverkko

#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define LINF 999999999999999999LL
#define N (1<<17)
#define M 1000000007

using namespace std;

vector<pair<int, ll>> v[100001];
ll e[100001];
ll w[100001];
bool b[100001];

ll pot (ll k) {
  if (k == 0) return 1;
  if (k % 2) return (2 * pot(k - 1)) % M;
  ll u = pot(k / 2);
  return (u * u) % M;
}

int main () {
  int n, m;
  cin>>n>>m;
  priority_queue<pair<ll, int>> q;
  for (int i = 0; i <= n; i++) e[i] = LINF;
  for (int i = 0; i < m; i++) {
    int a, b;
    ll c;
    cin>>a>>b>>c;
    v[a].push_back({b, c});
    v[b].push_back({a, c});
  }
  q.push({0, 1});
  e[1] = 0;
  while (!q.empty()) {
    int i = q.top().second;
    ll d = -q.top().first;
    q.pop();
    if (b[i]) continue;
    b[i] = true;
    for (auto p : v[i]) {
      int j = p.first;
      int c = d + p.second;
      if (e[j] > c) {
	e[j] = c;
	w[j] = 1;
	q.push({-c, j});
      } else if (e[j] == c) w[j]++;
    }
  }
  ll s = 0;
  for (int i : w) s += i;
  ll ans = pot(m - s);
  for (int i = 2; i <= n; i++) ans = (ans * (pot(w[i]) - 1)) % M;
  cout<<ans<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED