Submission #1076685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076685		KALARRY	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	290 ms	31204 KiB

commuter_pass

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const long long INF = 1e18;

long long N,M,dist[100005],S,T,U,V;
bool visited[100005],continained_in_best_path[100005];
vector<pair<long long,long long>> adj[100005];
vector<long long> free_edges[100005];
vector<long long> can_give_minimum[100005];

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);
        }
        for(auto u : free_edges[v])
            if(dist[u] > dist[v])
            {
                dist[u] = dist[v];
                q.push({-dist[u],u});
            }
    }
}

void dfs(long long v)
{
    if(continained_in_best_path[v]) //used also as visited
        return;
    continained_in_best_path[v] = true;
    for(auto u : can_give_minimum[v])
    {
        free_edges[u].push_back(v);
        dfs(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(S);
    dfs(T);
    long long ans = INF;
    Dijsktra(U);
    ans = dist[V];
    Dijsktra(V);
    ans = min(ans,dist[U]);
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

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

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