Task: | Tieverkko |
Sender: | Kuha |
Submission time: | 2016-07-28 14:59:09 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 100 |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.06 s | details |
#2 | ACCEPTED | 0.05 s | details |
#3 | ACCEPTED | 0.06 s | details |
#4 | ACCEPTED | 0.06 s | details |
#5 | ACCEPTED | 0.05 s | details |
#6 | ACCEPTED | 0.29 s | details |
#7 | ACCEPTED | 0.31 s | details |
#8 | ACCEPTED | 0.29 s | details |
#9 | ACCEPTED | 0.30 s | details |
#10 | ACCEPTED | 0.34 s | details |
Code
#include <bits/stdc++.h>#define ll long long#define INF 999999999#define LINF 999999999999999999LL#define N (1<<17)#define M 1000000007using 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 details
Test 1
Verdict: ACCEPTED
input |
---|
10 20 8 4 1 5 3 1 6 7 1 7 8 1 ... |
correct output |
---|
12096 |
user output |
---|
12096 |
Test 2
Verdict: ACCEPTED
input |
---|
10 20 5 10 1 9 10 2 1 2 1 3 4 2 ... |
correct output |
---|
3840 |
user output |
---|
3840 |
Test 3
Verdict: ACCEPTED
input |
---|
10 20 4 8 4 1 4 5 1 2 3 4 5 2 ... |
correct output |
---|
2048 |
user output |
---|
2048 |
Test 4
Verdict: ACCEPTED
input |
---|
10 20 8 9 8 4 6 6 9 6 3 9 10 1 ... |
correct output |
---|
3072 |
user output |
---|
3072 |
Test 5
Verdict: ACCEPTED
input |
---|
10 20 5 6 48 4 5 77 6 4 17 9 10 24 ... |
correct output |
---|
2048 |
user output |
---|
2048 |
Test 6
Verdict: ACCEPTED
input |
---|
100000 200000 47217 47144 1 74724 74725 1 36230 36260 1 5995 5996 1 ... |
correct output |
---|
741050064 |
user output |
---|
741050064 |
Test 7
Verdict: ACCEPTED
input |
---|
100000 200000 22251 22252 1 56527 56612 1 35801 35802 2 47446 47447 2 ... |
correct output |
---|
925428066 |
user output |
---|
925428066 |
Test 8
Verdict: ACCEPTED
input |
---|
100000 200000 21490 21480 2 6955 6956 8 3949 3938 4 71057 71058 3 ... |
correct output |
---|
601828864 |
user output |
---|
601828864 |
Test 9
Verdict: ACCEPTED
input |
---|
100000 200000 2001 2002 33 12041 12042 78 58901 58878 12 68010 68011 56 ... |
correct output |
---|
291634640 |
user output |
---|
291634640 |
Test 10
Verdict: ACCEPTED
input |
---|
100000 200000 74217 74238 380054461 43580 43581 786854520 62993 62970 636349519 63420 63478 975022059 ... |
correct output |
---|
215447033 |
user output |
---|
215447033 |