Submission #1118686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118686		Tai_xiu	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	314 ms	24172 KiB

commuter_pass

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

#define int long long
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
const Z maxn=200005;
Z n,m,s,t,toi,kurumi;
Z d1[maxn],d2[maxn],d3[maxn];
vii g[maxn];
void dijkstra1()
{
    memset(d1,0x3f3f3f3f,sizeof(d1));
    d1[s]=0;
    priority_queue<ii,vii,greater<ii>>q;
    q.push(mk(0,s));
    while(!q.empty()){
        ii top=q.top();q.pop();
        Z u=top.second;
        Z w=top.first;
        if (w>d1[u]) continue;
        for (ii i:g[u]){
            Z u1=i.first;
            Z w1=i.second;
            if (d1[u]+w1<d1[u1]){
                d1[u1]=d1[u]+w1;
                q.push(mk(d1[u1],u1));
            }
        }

    }
}
void dijkstra2()
{
    memset(d2,0x3f3f3f3f,sizeof(d2));
    d2[t]=0;
    priority_queue<ii,vii,greater<ii>>q;
    q.push(mk(0,t));
    while(!q.empty()){
        ii top=q.top();q.pop();
        Z u=top.second;
        Z w=top.first;
        if (w>d2[u]) continue;
        for (ii i:g[u]){
            Z u1=i.first;
            Z w1=i.second;
            if (d2[u]+w1<d2[u1]){
                d2[u1]=d2[u]+w1;
                q.push(mk(d2[u1],u1));
            }
        }

    }
}
Z ans=1e18;
void dijkstra3()
{
     memset(d3,0x3f3f3f3f,sizeof(d3));
    d3[toi]=0;
    priority_queue<ii,vii,greater<ii>>q;
    q.push(mk(0,toi));
    while(!q.empty()){
        ii top=q.top();q.pop();
        Z u=top.second;
        Z w=top.first;
        if (u==kurumi){
            ans=min(ans,w);
            return;
        }
        if (w>d3[u]) continue;
        for (ii i:g[u]){
            Z u1=i.first;
            Z w1=i.second;
            if (d1[u]+d2[u1]+w1==d1[t] ) w1=0;
            if (d3[u]+w1<d3[u1]){
                d3[u1]=d3[u]+w1;
                q.push(mk(d3[u1],u1));
            }
        }

    }
}
void dijkstra4()
{
     memset(d3,0x3f3f3f3f,sizeof(d3));
    d3[toi]=0;
    priority_queue<ii,vii,greater<ii>>q;
    q.push(mk(0,toi));
    while(!q.empty()){
        ii top=q.top();q.pop();
        Z u=top.second;
        Z w=top.first;
        if (u==kurumi){
            ans=min(ans,w);
            return;
        }
        if (w>d3[u]) continue;
        for (ii i:g[u]){
            Z u1=i.first;
            Z w1=i.second;
            if (d2[u]+d1[u1]+w1==d1[t] ) w1=0;
            if (d3[u]+w1<d3[u1]){
                d3[u1]=d3[u]+w1;
                q.push(mk(d3[u1],u1));
            }
        }

    }
}
void dijkstra5()
{
     memset(d3,0x3f3f3f3f,sizeof(d3));
    d3[kurumi]=0;
    priority_queue<ii,vii,greater<ii>>q;
    q.push(mk(0,kurumi));
    while(!q.empty()){
        ii top=q.top();q.pop();
        Z u=top.second;
        Z w=top.first;
        if (u==toi){
            ans=min(ans,w);
            return;
        }
        if (w>d3[u]) continue;
        for (ii i:g[u]){
            Z u1=i.first;
            Z w1=i.second;
            if (d1[u]+d2[u1]+w1==d1[t] ) w1=0;
            if (d3[u]+w1<d3[u1]){
                d3[u1]=d3[u]+w1;
                q.push(mk(d3[u1],u1));
            }
        }

    }
}
void dijkstra6()
{
     memset(d3,0x3f3f3f3f,sizeof(d3));
    d3[kurumi]=0;
    priority_queue<ii,vii,greater<ii>>q;
    q.push(mk(0,kurumi));
    while(!q.empty()){
        ii top=q.top();q.pop();
        Z u=top.second;
        Z w=top.first;
        if (u==toi){
            ans=min(ans,w);
            return;
        }
        if (w>d3[u]) continue;
        for (ii i:g[u]){
            Z u1=i.first;
            Z w1=i.second;
            if (d2[u]+d1[u1]+w1==d1[t] ) w1=0;
            if (d3[u]+w1<d3[u1]){
                d3[u1]=d3[u]+w1;
                q.push(mk(d3[u1],u1));
            }
        }

    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen("commuter.inp","r",stdin);
//    freopen("commuter.out","w",stdout);
    cin>>n>>m>>s>>t;
    cin>>toi>>kurumi;
    FOR(i,1,m){
        Z u,v,w;
        cin>>u>>v>>w;;
        g[u].pb(mk(v,w));
        g[v].pb(mk(u,w));
    }
    dijkstra1();
    dijkstra2();
    dijkstra3();
    dijkstra4();
    dijkstra5();
    dijkstra6();
    cout<<ans;
}

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