Submission #1077832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077832		KALARRY	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	325 ms	39972 KiB

commuter_pass

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const long long INF = 1e18;

long long N,M,dist[100005],dist_U[100005],dist_V[100005],S,T,U,V;
bool visited[100005];
vector<pair<long long,long long>> adj[100005];
vector<long long> can_give_minimum[100005],free_edges[100005],reverse_free[100005]; //tthe DUG but reverse

void Dijsktra(long long start)
{
    for(long long i = 1 ; i <= N ; i++)
    {
        dist[i] = INF;
        visited[i] = false;
        can_give_minimum[i].clear();
    }
    dist[start] = 0;
    priority_queue<pair<long long,long long>> q;
    q.push({0,start});
    while(!q.empty())
    {
        long long v = q.top().second;
        q.pop();
        if(visited[v])
            continue;
        visited[v] = true;
        for(auto e : adj[v])
        {
            long long u = e.first;
            long long w = e.second;
            if(dist[v] + w < dist[u])
            {
                dist[u] = dist[v] + w;
                can_give_minimum[u].clear();
                can_give_minimum[u].push_back(v);
                q.push({-dist[u],u});
            }
            else if(dist[v] + w == dist[u])
                can_give_minimum[u].push_back(v);
        }
    }
}

void direct_egdes(long long v)
{
    if(visited[v])
        return;
    visited[v] = true;
    for(auto u : can_give_minimum[v])
    {
        free_edges[u].push_back(v);
        reverse_free[v].push_back(u);
        direct_egdes(u);
    }
}

void dfs_enter(long long v)
{
    if(visited[v])
        return;
    visited[v] = true;
    for(auto u : reverse_free[V]) //basically reverse free edges
    {
        dfs_enter(u);
        dist_U[v] = min(dist_U[v],dist_U[u]); 
    }
}

void dfs_leave(long long v)
{
    if(visited[v]) //used also as visited
        return;
    visited[v] = true;
    for(auto u : free_edges[v])
    {
        dfs_leave(u);
        dist_V[v] = min(dist_V[v],dist_V[u]);
    }
}

int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&N,&M,&S,&T,&U,&V);
    for(long long a,b,w,i = 1 ; i <= M ; i++)
    {
        scanf("%lld%lld%lld",&a,&b,&w);
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }
    Dijsktra(U);
    for(int i = 1 ; i <= N ; i++)
        dist_U[i] = dist[i];
    long long ans = dist[V];
    Dijsktra(V);
    for(int i = 1 ; i <= N ; i++)
        dist_V[i] = dist[i];
    Dijsktra(S);
    memset(visited,false,sizeof(visited));
    direct_egdes(T);
    memset(visited,false,sizeof(visited));
    for(int i = 1 ; i <= N ; i++)
        dfs_enter(i);
    memset(visited,false,sizeof(visited));
    for(int i = 1 ; i <= N ; i++)
        dfs_leave(i);
    for(int i = 1 ; i <= N ; i++)
        ans = min(ans,dist_U[i] + dist_V[i]);
    swap(U,V);
    Dijsktra(U);
    for(int i = 1 ; i <= N ; i++)
        dist_U[i] = dist[i];
    Dijsktra(V);
    for(int i = 1 ; i <= N ; i++)
        dist_V[i] = dist[i];
    memset(visited,false,sizeof(visited));
    for(int i = 1 ; i <= N ; i++)
        dfs_enter(i);
    memset(visited,false,sizeof(visited));
    for(int i = 1 ; i <= N ; i++)
        dfs_leave(i);
    for(int i = 1 ; i <= N ; i++)
        ans = min(ans,dist_U[i] + dist_V[i]);
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%lld%lld%lld%lld%lld%lld",&N,&M,&S,&T,&U,&V);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%lld%lld%lld",&a,&b,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45