Submission #1232476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232476		hoa208	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	237 ms	29356 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,b,a) for(int i=(b);i>=(a);i--)
#define pa pair<ll,ll>
#define fi first
#define se second
#define bit(mask,j) (mask&(1<<j))
#define hoabanmatuy ios_base::sync_with_stdio(false);cin.tie(0);
const ll INF=1e15;
const ll N=1e5+10;
const ll M=2e5+10;
ll n,m,ans=INF;
ll S,T,U,V;
vector<pa> g[N];
ll d_st[N],mark_st[N];
void dextra(ll s,ll t)
{
    memset(d_st,0x3f,sizeof d_st);
    memset(mark_st,0,sizeof mark_st);
    priority_queue<pa,vector<pa>,greater<pa>> q;
    q.push({0,s});
    d_st[s]=0;
    mark_st[s]=0;
    while(!q.empty())
    {
        ll u=q.top().se;
        q.pop();
        if(mark_st[u]) continue;
        mark_st[u]=1;
        for(auto e:g[u])
        {
            ll v=e.fi,w=e.se;
            if(d_st[v]>d_st[u]+w)
            {
                d_st[v]=d_st[u]+w;
                q.push({d_st[v],v});
            }
        }
    }
    memset(mark_st,0,sizeof mark_st);
    queue<ll> trace;
    trace.push(t);
    mark_st[t]=1;
    while(!trace.empty())
    {
        ll u=trace.front();
        trace.pop();
        for(auto e:g[u])
        {
            ll v=e.fi,w=e.se;
            if(mark_st[v]==0 && d_st[v]+w==d_st[u])
            {
                mark_st[v]=1;
                trace.push(v);
            }
        }
    }
    /* FOR(i,1,n)
        if(mark_st[i]==1)
            cout<<i<<' ';
    cout<<'\n'; */
}
ll mark_uv[N][3],d_uv[N][3];
void slove()
{
    memset(d_uv,0x3f,sizeof d_uv);
    memset(mark_uv,0,sizeof mark_uv);
    priority_queue<pair<ll,pa>,vector<pair<ll,pa>>,greater<pair<ll,pa>>> q;
    q.push({0,{U,0}});
    d_uv[U][0]=0;
    while(!q.empty())
    {
        ll u=q.top().se.fi,t=q.top().se.se;
        q.pop();
        if(u==V)
        {
            ans=min(d_uv[u][t],ans);
            return;
        }
        if(mark_uv[u][t]) continue;
        mark_uv[u][t]=1;
        for(auto e:g[u])
        {
            ll v=e.fi,w=e.se;
            if(t!=2 && d_st[v]==d_st[u]+w && mark_st[v]==1) 
            {
                ll t2=t|1;
                if(d_uv[v][t2]>d_uv[u][t])
                {
                    d_uv[v][t2]=d_uv[u][t];
                    q.push({d_uv[v][t2],{v,t2}});
                }
            }
            ll t1=t;if(t==1) t1=2;
            if(d_uv[v][t1]>d_uv[u][t]+w)
            {
                d_uv[v][t1]=d_uv[u][t]+w;
                q.push({d_uv[v][t1],{v,t1}});
            }
        }
    }
}
int main ()
{
    hoabanmatuy
    if(fopen("hbmt.inp", "r")) {
            freopen("hbmt.inp", "r", stdin);
            freopen("hbmt.out", "w", stdout);
        }
    cin>>n>>m;
    cin>>S>>T;
    cin>>U>>V;
    FOR(i,1,m)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    FOR(i,0,1)
    {
        dextra(S,T);
        slove();
        swap(S,T);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:110:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |             freopen("hbmt.inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:111:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |             freopen("hbmt.out", "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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