Submission #1322187

#TimeUsernameProblemLanguageResultExecution timeMemory
1322187ninstroyerConstruction Project 2 (JOI24_ho_t2)C++20
45 / 100
2095 ms18916 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll nx = 2e5+5, inf = 4e18;

ll n,m,s,t,l,k,cnt;
vector<pair<int,ll>> adj[nx];

vector<ll> dijkstra(int st)
{
    vector<ll> dist(n+1,inf);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    dist[st] = 0;
    pq.push({0,st});
    while(!pq.empty())
    {
        auto [d, u] =  pq.top();
        pq.pop();
        if(d > dist[u]) continue;
        for(auto [v,w] : adj[u])
        {
            if(d+w < dist[v])
            {
                dist[v] = d+w;
                pq.push({dist[v],v});
            }
        }
    }
    return dist;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>s>>t>>l>>k;
    for(int i = 1; i <= m; i++)
    {
        int u,v; ll w; cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    vector<ll> distS = dijkstra(s);
    vector<ll> distT = dijkstra(t);
    if(distS[t] <= k)
    {
        cout<<n*(n-1)/2;
        return 0;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = i+1; j <= n; j++)
        {
            if(distS[i] + l + distT[j] <= k || distS[j] + l + distT[i] <= k) cnt++;
        }
    }
    cout<<cnt;
 }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...