4037 | 2023. 03. 09 14:01:19 | gortomi | Barátnők (50 pont) | cpp17 | Elfogadva 50/50 | 136ms | 26260 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int MOD = 1e9 + 7;
vector<vector<pii > > g;
void dfs(int n, vector<int> & w, vector<int> & d, int go)
{
if(w[n] != -1) return;
w[n] = 0;
if(go == n)
{
w[n] = 1;
return;
}
for(auto x : g[n])
{
if(x.second + d[n] == d[x.first])
{
dfs(x.first, w, d, go);
w[n] += w[x.first];
w[n] %= MOD;
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(m), b(m), c(m);
vector<int> w1(n + 1, -1), w2(n + 1, -1);
g.resize(n + 1);
for(int i = 0; i < m; i++)
{
int x, y, z;
cin >> x >> y >> z;
a[i] = x;
b[i] = y;
c[i] = z;
g[x].push_back({y, z});
g[y].push_back({x, z});
}
int s, f;
cin >> s >> f;
priority_queue<pii, vector<pii >, greater<pii > > pq;
vector<int> d1(n + 1, 1e15), d2(n + 1, 1e15);
d1[s] = 0;
pq.push({0, s});
while(!pq.empty())
{
int v = pq.top().second, d_v = pq.top().first;
pq.pop();
if(d_v != d1[v]) continue;
for(auto x : g[v])
{
int to = x.first, len = x.second;
if(d1[to] > d1[v] + len)
{
d1[to] = d1[v] + len;
pq.push({d1[to], to});
}
}
}
d2[f] = 0;
pq.push({0, f});
while(!pq.empty())
{
int v = pq.top().second, d_v = pq.top().first;
pq.pop();
if(d_v != d2[v]) continue;
for(auto x : g[v])
{
int to = x.first, len = x.second;
if(d2[to] > d2[v] + len)
{
d2[to] = d2[v] + len;
pq.push({d2[to], to});
}
}
}
dfs(s, w2, d1, f);
dfs(f, w1, d2, s);
for(int i = 0; i <= n; i++)
{
if(w1[i] == -1) w1[i] = 0;
if(w2[i] == -1) w2[i] = 0;
}
int ans = w2[s] * w2[s];
for(int i = 0; i < m; i++)
{
int x = a[i], y = b[i], z = c[i];
if(d1[x] > d1[y]) swap(x, y);
if(d1[x] + z != d1[y]) continue;
if(d1[x] < d2[x] && d1[y] > d2[y])
{
int d = w1[x] * w2[y];
d %= MOD;
d *= d;
d %= MOD;
ans -= d;
ans %= MOD;
}
}
for(int i = 1; i <= n; i++)
{
if(d1[i] == d2[i])
{
int d = w1[i] * w2[i];
d %= MOD;
d *= d;
d %= MOD;
ans -= d;
ans %= MOD;
}
}
ans += MOD;
ans %= MOD;
cout << ans;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 136ms | 23288 KiB | |||
3 | Elfogadva | 2/2 | 4ms | 2656 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2712 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2824 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 3048 KiB | |||
7 | Elfogadva | 2/2 | 4ms | 3208 KiB | |||
8 | Elfogadva | 1/1 | 48ms | 15732 KiB | |||
9 | Elfogadva | 2/2 | 75ms | 24820 KiB | |||
10 | Elfogadva | 2/2 | 97ms | 23396 KiB | |||
11 | Elfogadva | 2/2 | 96ms | 24128 KiB | |||
12 | Elfogadva | 2/2 | 87ms | 24556 KiB | |||
13 | Elfogadva | 2/2 | 103ms | 23912 KiB | |||
14 | Elfogadva | 2/2 | 98ms | 24964 KiB | |||
15 | Elfogadva | 2/2 | 97ms | 25492 KiB | |||
16 | Elfogadva | 1/1 | 108ms | 24704 KiB | |||
17 | Elfogadva | 1/1 | 114ms | 25296 KiB | |||
18 | Elfogadva | 1/1 | 54ms | 16972 KiB | |||
19 | Elfogadva | 2/2 | 112ms | 25544 KiB | |||
20 | Elfogadva | 2/2 | 112ms | 24224 KiB | |||
21 | Elfogadva | 2/2 | 116ms | 24940 KiB | |||
22 | Elfogadva | 2/2 | 98ms | 24684 KiB | |||
23 | Elfogadva | 2/2 | 112ms | 25920 KiB | |||
24 | Elfogadva | 2/2 | 83ms | 24632 KiB | |||
25 | Elfogadva | 2/2 | 78ms | 23088 KiB | |||
26 | Elfogadva | 2/2 | 103ms | 25148 KiB | |||
27 | Elfogadva | 2/2 | 108ms | 25520 KiB | |||
28 | Elfogadva | 2/2 | 112ms | 26260 KiB | |||
29 | Elfogadva | 2/2 | 103ms | 24844 KiB |