Submission #389776

#	Time	Username	Problem	Language	Result	Execution time	Memory
389776		cpp219	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	83 ms	22736 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll inf = 1e16 + 7;

struct Edge{
    ll u,v,w;
};
Edge a[N];
ll S,T,U,V,n,m,u,v,w,d[N],D[2][N],dp[N][5];
vector<LL> g[N];

void Dij(ll scr,ll cond){
    fill(d,d + n + 1,inf); d[scr] = 0;
    priority_queue<LL,vector<LL>,greater<LL>> pq; pq.push({0,scr});
    while(!pq.empty()){
        LL t = pq.top(); pq.pop();
        ll u = t.sc;
        for (auto i : g[u]){
            ll v = i.fs,L = i.sc;
            if (d[v] > d[u] + L) d[v] = d[u] + L,pq.push({d[v],v});
        }
    }
    for (ll i = 1;i <= n;i++) D[cond][i] = d[i];
}

bool Is_in(ll u,ll v,ll w){
    ll lens = D[0][T];
    if (D[0][u] + D[1][v] + w == lens||D[0][v] + D[1][u] + w == lens) return 1;
    return 0;
}

bool direct(ll u,ll v){
    return (D[0][u] < D[0][v]);
}

struct Node{
    ll val,cur,cond;
};

bool operator < (Node a,Node b){
    return a.val > b.val;
}
priority_queue<Node> pq;

void update(ll u,ll cond,ll val){
    if (dp[u][cond] <= val) return;
    dp[u][cond] = val; pq.push({val,u,cond});
}

/// 0 not in    1 in but small -> big   2 in but big -> small     3 out
void Find_opt(ll scr){
    for (ll i = 1;i <= n;i++)
        for (ll j = 0;j < 5;j++) dp[i][j] = inf;
    dp[scr][0] = 0; pq.push({0,scr,0});
    while(!pq.empty()){
        Node t = pq.top(); pq.pop();
        ll u = t.cur,now = t.cond;
        for (auto i : g[u]){
            ll v = i.fs,L = i.sc;
            if (Is_in(u,v,L)){
                if (!now){
                    if (direct(u,v)) update(v,1,dp[u][now]);
                    else update(v,2,dp[u][now]);
                }
                if (now == 1 && direct(u,v)) update(v,1,dp[u][now]);
                if (now == 2 && !direct(u,v)) update(v,2,dp[u][now]);
            }
            ll nxt = now;
            if (now == 1 || now == 2) nxt = 3;
            if (dp[v][nxt] > dp[u][now] + L) dp[v][nxt] = dp[u][now] + L,pq.push({dp[v][nxt],v,nxt});
        }
    }
    //cout<<direct(3,2); exit(0);
    //cout<<dp[4][0]<<" "<<dp[1][1]<<" "<<dp[4][2]<<" "<<dp[4][3]; exit(0);
    cout<<min(min(dp[V][0],min(dp[V][1],dp[V][2])),dp[V][3]);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>m>>S>>T>>U>>V;
    for (ll i = 1;i <= m;i++){
        cin>>u>>v>>w; a[i] = {u,v,w};
        g[u].push_back({v,w}); g[v].push_back({u,w});
    }
    Dij(S,0); Dij(T,1); Find_opt(U);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   88 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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