Submission #132485

#	Time	Username	Problem	Language	Result	Execution time	Memory
132485		ksmzzang2003	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	712 ms	25684 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define INF (1LL<<60)
typedef long long ll;
typedef pair <int,int> pii;
int N,M,S,T,U,V,deg[101010];
ll du[101010],dv[101010],d[101010],disu[101010],disv[101010],dist[101010];
vector <pii> adj[101010];
vector <int> dag[101010];

struct Data{
    int u,v ; ll w ;
    bool operator<(const Data &r)const{
        return w>r.w;
    }
};
priority_queue <Data> pq;
queue <int> q;
int main(){
    scanf("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
    for(int i=1;i<=M;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        adj[u].push_back(pii(v,w));
        adj[v].push_back(pii(u,w));
    }
    for(int i=1;i<=N;i++) dist[i] = INF;
    pq.push(Data{0,S,0});
    while(!pq.empty()){
        Data t = pq.top(); pq.pop();
        if(t.w<=dist[t.v]) deg[t.v]++, dag[t.u].push_back(t.v);
        if(t.w>=dist[t.v]) continue;
        dist[t.v] = t.w;
        for(pii nx: adj[t.v]) pq.push((Data){t.v,nx.first,nx.second+t.w});
    }
    for(int i=1;i<=N;i++) disu[i] = INF;
    pq.push(Data{0,U,0});
    while(!pq.empty()){
        Data t = pq.top();
        pq.pop();
        if (t.w >= disu[t.v]) continue;
        disu[t.v] = t.w;
        for (pii nx : adj[t.v]) pq.push((Data){t.v, nx.first, nx.second+t.w});
    }
    for(int i=1;i<=N;i++) disv[i] = INF;
    pq.push(Data{0,V,0});
    while(!pq.empty()){
        Data t = pq.top();
        pq.pop();
        if(t.w>=disv[t.v]) continue;
        disv[t.v] = t.w;
        for(pii nx:adj[t.v]) pq.push((Data){t.v,nx.first,nx.second+t.w});
    }

    q.push(S);
    for(int i=1;i<=N;i++) du[i] = disu[i],dv[i] = disv[i],d[i] = INF;
    while(!q.empty()){
        int u = q.front(); q.pop();
        d[u] = min(d[u],du[u]+disv[u]);
        d[u] = min(d[u],dv[u]+disu[u]);
        for(int v:dag[u]){
            d[v] = min(d[v],d[u]);
            du[v] = min(du[v],du[u]);
            dv[v] = min(dv[v],dv[u]);
            deg[v]--; if(deg[v]==0) q.push(v);
        }
    }
    printf("%lld\n",min(d[T],disu[V]));
}

Compilation message (stderr)

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

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