Submission #359034

#	Time	Username	Problem	Language	Result	Execution time	Memory
359034		shahriarkhan	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	454 ms	25384 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std ;

const int mx = 1e5 + 5 ;

const long long INF = 1e18 ;

typedef pair<long long , int> li ;

vector<pair<int,long long> > adj[mx] ;

long long dp1[mx] , dp2[mx] , dist_s[mx] , dist_t[mx] , dist_u[mx] , dist_v[mx] , ans = INF ;

int vis[mx] , n , m ;

void djikstra1(int start , long long dist[])
{
    for(int i = 1 ; i <= n ; ++i) dist[i] = INF , vis[i] = 0 ;
    priority_queue<li,vector<li>,greater<li> > pq ;
    pq.push({0,start}) , dist[start] = 0 ;
    while(!pq.empty())
    {
        int u = pq.top().second ;
        long long cost = pq.top().first ;
        pq.pop() ;
        if(vis[u]) continue ;
        vis[u] = 1 ;
        for(auto p : adj[u])
        {
            int v = p.first ;
            long long w = p.second ;
            if(dist[v] > (cost + w))
            {
                dist[v] = cost + w ;
                pq.push({dist[v],v}) ;
            }
        }
    }
    return ;
}

void djikstra2(int s , long long dp[] , long long dist[])
{
    for(int i = 1 ; i <= n ; ++i)
    {
        dp[i] = dist_u[i] ;
        dist[i] = INF ;
        vis[i] = 0 ;
    }
    priority_queue<li,vector<li>,greater<li> > pq ;
    pq.push({0,s}) , dist[s] = 0 ;
    while(!pq.empty())
    {
        int u = pq.top().second ; long long cost = pq.top().first ;
        pq.pop() ;
        if(vis[u]) continue ;
        vis[u] = 1 ;
        for(auto p : adj[u])
        {
            int v = p.first ; long long w = p.second ;
            if(dist[v] == (cost+w)) dp[v] = min(dp[v],dp[u]) ;
            else if(dist[v] > (cost+w))
            {
                dist[v] = cost + w ;
                dp[v] = min(dist_u[v],dp[u]) ;
                pq.push({dist[v],v}) ;
            }
        }
    }
    return ;
}

int main()
{
    scanf("%d%d",&n,&m) ;
    int s , t ;
    scanf("%d%d",&s,&t) ;
    int u , v ;
    scanf("%d%d",&u,&v) ;
    for(int i = 1 ; i <= m ; ++i)
    {
        int a , b ;
        long long c ;
        scanf("%d%d%lld",&a,&b,&c) ;
        adj[a].push_back({b,c}) ;
        adj[b].push_back({a,c}) ;
    }
    djikstra1(u,dist_u) ;
    djikstra1(v,dist_v) ;
    djikstra2(s,dp1,dist_s) ;
    djikstra2(t,dp2,dist_t) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(dist_s[t]==(dist_s[i] + dist_t[i]))
        {
            ans = min(ans,dist_v[i] + min(dp1[i],dp2[i])) ;
        }
    }
    printf("%lld\n",min(ans,dist_u[v])) ;
    return 0 ;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |     scanf("%d%d",&n,&m) ;
      |     ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%d%d",&s,&t) ;
      |     ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |     scanf("%d%d",&u,&v) ;
      |     ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         scanf("%d%d%lld",&a,&b,&c) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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