Submission #727759

#	Time	Username	Problem	Language	Result	Execution time	Memory
727759		fdnfksd	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	330 ms	54192 KiB

commuter_pass

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,d[3][maxN];
bool vis[maxN];
vector<pli>g[maxN],adj[maxN],ke[maxN];
void dij(ll s,ll t)
{
    for(int i=1;i<=n;i++) d[t][i]=inf,vis[i]=false;
    d[t][s]=0;
    priority_queue<pli,vector<pli>,greater<pli>>pq;
    pq.push({d[t][s],s});
    while(!pq.empty())
    {
        ll u=pq.top().se;
        pq.pop();
        if(vis[u]==true) continue;
        vis[u]=true;
        for(auto vv:g[u])
        {
            ll v=vv.fi;
            ll w=vv.se;
            if(d[t][v]>d[t][u]+w)
            {
                d[t][v]=d[t][u]+w;
                pq.push({d[t][v],v});
            }
        }
    }
}
ll m,s,t,x,y;
struct qq
{
    ll u,v,w;

}a[maxN];
void solve()
{
    cin >> n >> m;
    cin >> s >> t;
    cin >> x >> y;
    for(int i=1;i<=m;i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        a[i].u=u;
        a[i].v=v;
        a[i].w=w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    dij(s,0);
    dij(t,1);
    for(int i=1;i<=m;i++)
    {
        if(d[0][a[i].u]+d[1][a[i].v]+a[i].w==d[0][t])
        {
            adj[a[i].u].pb({a[i].v,0});
            adj[a[i].v].pb({a[i].u,a[i].w});
        }
        else if(d[0][a[i].v]+d[1][a[i].u]+a[i].w==d[0][t])
        {
            adj[a[i].v].pb({a[i].u,0});
            adj[a[i].u].pb({a[i].v,a[i].w});
        }
        else
        {
            adj[a[i].u].pb({a[i].v,a[i].w});
            adj[a[i].v].pb({a[i].u,a[i].w});
        }
    }
    for(int i=1;i<=n;i++) swap(adj[i],g[i]);
    ll ans=inf;
    dij(x,0);
    ans=d[0][y];
    for(int i=1;i<=n;i++) swap(ke[i],g[i]);
    dij(x,0);
    ans=min(ans,d[0][y]);
    cout << ans <<'\n';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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