Submission #680318

#	Time	Username	Problem	Language	Result	Execution time	Memory
680318		kakayoshi	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	501 ms	41516 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define forw(i,a,b) for(int i=a;i<=b;i++)
#define forb(i,a,b) for(int i=a;i>=b;i--)
#define pu push
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(),a.end()
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,pair<ll,ll> > plll;
const ll maxN=2e5+5;
const ll oo=1e18;
ll n,m,s,t,u,v,d[305][305],dist[maxN][5],way[maxN][5];
vector <plll> save;
vector <pll> edge[maxN];
void dijk(int s, int id)
{
    forw(i,1,n) dist[i][id]=oo;
    dist[s][id]=0;
    way[s][id]=1;
    priority_queue<pll,vector <pll> , greater<pll> > p;
    p.pu({0,s});
    while (p.size())
    {
        ll val=p.top().fi;
        ll u=p.top().se;
        p.pop();
        if (val>dist[u][id]) continue;
        for(auto tmp:edge[u])
        {
            ll v=tmp.se; ll add=tmp.fi;
            if (val+add<dist[v][id])
            {
                way[v][id]=way[u][id];
                dist[v][id]=val+add;
                p.pu({dist[v][id],v});
            }
            else
                if (val+add==dist[v][id]) way[v][id]+=way[u][id];
        }
    }
    return;
}
void init()
{
    forw(i,1,m)
    {
        ll u,v,z;
        z=save[i-1].fi; u=save[i-1].se.fi; v=save[i-1].se.se;
        edge[u].pb({z,v});
        edge[v].pb({z,u});
    }
    dijk(s,0);
    dijk(t,1);
    return;
}
void sub1()
{
    //cout<<"subtask 1\n";
    dijk(v,2);
    ll ans=dist[u][2];
    forw(i,1,n)
    if (dist[i][0]+dist[i][1]==dist[t][0])
        ans=min(ans,dist[i][2]);
    cout<<ans;
    return;
}
void sub2()
{
    //cout<<"subtask 2\n";
    for(auto tmp:save)
    {
        ll u=tmp.se.fi;
        ll v=tmp.se.se;
        ll val=tmp.fi;
        if (dist[u][0]+val+dist[v][1]==dist[t][0] || dist[u][1]+val+dist[v][0]==dist[t][0])
        {
            edge[u].pb({0,v});
            edge[v].pb({0,u});
        }
    }
    dijk(u,2);
    cout<<dist[v][2];
    return;
}
void sub3()
{
    //cout<<"subtask 3\n";
    forw(i,1,n)
    forw(j,1,n)
        if (i!=j) d[i][j]=oo;
    forw(i,1,m)
    {
        ll u,v,z;
        z=save[i-1].fi; u=save[i-1].se.fi; v=save[i-1].se.se;
        d[u][v]=d[v][u]=min(d[u][v],z);
    }
    forw(k,1,n)
    forw(i,1,n)
    forw(j,1,n)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    vector <pii> pend;
    forw(i,1,n)
    forw(j,1,n)
    if (d[s][i]+d[i][j]+d[j][t]==d[s][t])
        pend.pb({i,j});
    for(auto tmp:pend)
        d[tmp.fi][tmp.se]=d[tmp.se][tmp.fi]=0;
    ll ans=d[u][v];
    forw(i,1,n)
    forw(j,1,n)
        ans=min(ans,d[u][i]+d[i][j]+d[j][v]);
    cout<<ans;
    return;
}
int main()
{
    ios::sync_with_stdio();
    cin.tie(0);
    //freopen("b.inp","r",stdin);
    //freopen("b.out","w",stdout);
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    forw(i,1,m)
    {
        ll u,v,z; cin>>u>>v>>z;
        save.pb({z,{u,v}});
    }
    init();
    if (s==u) sub1();
    else
        if (way[t][0]==1) sub2();
        else sub3();
    return 0;
}

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