Submission #1085198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085198		DucNguyen2007	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	205 ms	38224 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=2e5+5;
const ll inf=2e18;
int n,m,a,b,c,d;
struct duongdi
{
    int u;
    ll w;
    bool operator < (const duongdi &o)const
    {
        return w>o.w;
    }
};
struct canh
{
    int u,v;
    ll w;
}p[maxN+1];
priority_queue<duongdi> pq;
ll dist[4][maxN+1],dp1[maxN+1],dp2[maxN+1];
bool vis[maxN+1];
vector<duongdi> adj[maxN+1];
vector<int> dadj[maxN+1],topo;
void dijkstra(int x,int type)
{
    for(int i=1;i<=n;i++)
    {
        dist[type][i]=inf;
    }
    dist[type][x]=0;
    pq.push({x,0});
    //cout<<x<<" "<<cd(x)<<'\n';
    x=type;
    while(!pq.empty())
    {
        duongdi tmp=pq.top();
        pq.pop();
        int u=tmp.u;
        ll w=tmp.w;
        if(dist[x][u]<w)
        {
            continue;
        }
        for(auto i:adj[u])
        {
            int v=i.u;
            if(dist[x][v]>dist[x][u]+i.w)
            {
                dist[x][v]=dist[x][u]+i.w;
                pq.push({v,dist[x][v]});
            }
        }
    }
}
void dfs(int u)
{
    vis[u]=true;
    for(auto v:dadj[u])
    {
        if(!vis[v])
        {
            dfs(v);
        }
    }
    topo.push_back(u);
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>a>>b>>c>>d;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        ll w;
        cin>>u>>v>>w;
        p[i].u=u;
        p[i].v=v;
        p[i].w=w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dijkstra(a,0);
    dijkstra(b,1);
    dijkstra(c,2);
    dijkstra(d,3);
    for(int i=1;i<=m;i++)
    {
        int u=p[i].u,v=p[i].v;
        ll w=p[i].w;
        if(dist[0][u]+w+dist[1][v]==dist[0][b])
        {
            dadj[u].push_back(v);
            //cout<<u<<" "<<v<<'\n';
        }
        else if(dist[0][v]+w+dist[1][u]==dist[0][b])
        {
            dadj[v].push_back(u);
        }
    }
    memset(vis,false,sizeof(vis));
    dfs(a);
    reverse(topo.begin(),topo.end());
    for(int i=1;i<=n;i++)
    {
        dp1[i]=dp2[i]=inf;
    }
    for(auto u:topo)
    {
        dp1[u]=min(dp1[u],dist[2][u]);
        dp2[u]=min(dp2[u],dist[3][u]);
        //cout<<u<<'\n';
        for(auto v:dadj[u])
        {
            dp1[v]=min(dp1[v],dp1[u]);
            dp2[v]=min(dp2[v],dp2[u]);
            //cout<<v<<" "<<dp1[v]<<" "<<dp1[u]<<'\n';
        }
    }
    //cout<<'\n';
    ll ans=dist[2][d];
   // cout<<ans<<'\n';
    for(int i=1;i<=n;i++)
    {
        ans=min(ans,min(dp1[i]+dist[3][i],dp2[i]+dist[2][i]));
        //cout<<i<<" "<<dp1[i]<<" "<<dp2[i]<<'\n';
    }
    cout<<ans;
}

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