40362023-03-09 13:55:55gortomiBarátnők (50 pont)cpp17Hibás válasz 13/50120ms26352 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])
        {
            ans -= w1[x] * w2[y] * w1[x] * w2[y];
            ans %= MOD;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(d1[i] == d2[i])
        {
            ans -= w1[i] * w2[i] * w1[i] * w2[i];
            ans %= MOD;
        }
    }
    ans += MOD;
    ans %= MOD;
    cout << ans;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base13/50
1Elfogadva0/03ms2104 KiB
2Hibás válasz0/0112ms23548 KiB
3Hibás válasz0/23ms2500 KiB
4Hibás válasz0/23ms2692 KiB
5Elfogadva2/23ms2676 KiB
6Hibás válasz0/23ms2984 KiB
7Hibás válasz0/23ms3324 KiB
8Elfogadva1/148ms16228 KiB
9Elfogadva2/278ms25280 KiB
10Hibás válasz0/290ms23772 KiB
11Hibás válasz0/286ms24032 KiB
12Elfogadva2/283ms24700 KiB
13Hibás válasz0/287ms23888 KiB
14Hibás válasz0/290ms24880 KiB
15Hibás válasz0/287ms25484 KiB
16Elfogadva1/1107ms24804 KiB
17Hibás válasz0/1111ms25252 KiB
18Elfogadva1/152ms16972 KiB
19Hibás válasz0/2115ms25476 KiB
20Hibás válasz0/2107ms24008 KiB
21Hibás válasz0/2119ms24816 KiB
22Elfogadva2/298ms24500 KiB
23Hibás válasz0/2120ms25996 KiB
24Hibás válasz0/285ms24516 KiB
25Hibás válasz0/278ms23052 KiB
26Hibás válasz0/2101ms25344 KiB
27Hibás válasz0/2112ms25612 KiB
28Elfogadva2/2112ms26352 KiB
29Hibás válasz0/2108ms25020 KiB