Submission #1219022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219022		abdelhakim	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2097 ms	44880 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)(1e10)
#define mod (ll)(1e9 + 7)
#define dbg(x) cerr<<#x << ' ' << x << endl;
using v = vector<vector<vector<ll>>>;
ll sum(ll a, ll b)
{
    cout << a-b << endl;
    return a+b;
}
void printvec(vector<ll>& a)
{
    ll n=a.size();
    for (int i=0;i<n;i++)
    {
        cout <<a[i] << ' ';
    }
    cout << endl;
}
ll gcd(ll a, ll b)
{
    if(b>a)swap(a,b);
    if(b==0)return a;
    return gcd(a%b,b);
}
vector<ll> dijkstra(vector<vector<pair<ll,ll>>>& adj, ll src, ll n)
{
    vector<ll> dist(n,inf);
    dist[src]=0;
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    pq.push({0,src});
    while(!pq.empty())
    {
        pair<ll,ll> node=pq.top();
        pq.pop();
        for (auto &&e : adj[node.second])
        {
            if(dist[e.first]>node.first+e.second)
            {
                dist[e.first]=node.first+e.second;
                pq.push({dist[e.first],e.first});
            }
        }
    }
    return dist;
}
vector<ll> ud;
vector<ll> sd;
vector<ll> td;
vector<ll> vd;
vector<pair<ll,ll>> dp;
ll ans=inf;
void dfs(ll node, vector<vector<pair<ll,ll>>>& adj, ll cost, pair<ll,ll> curm, ll l3iba, ll t)
{
    if((cost!=sd[node]) || (cost+td[node]!=l3iba))return;
    if(node==t)
    {
        ans=min(ans,curm.first+curm.second);
    }
    if(dp[node].first!=-1) return;
    ll v1=ud[node];
    ll v2=vd[node];
    for (auto &&e : adj[node])
    {
        ll val1=ud[e.first];
        dbg(e.first);
        ll val2=vd[e.first];
        dbg(val2);
        dfs(e.first,adj,cost+e.second,{min(curm.first,val1),min(curm.second,val2)},l3iba,t);
        if(dp[e.first].first==-1)continue;
        
        if(dp[node].first==-1)
        {
            dp[node].first=min(v1,dp[e.first].first);
            dp[node].second=min(v2,dp[e.first].second);
        }
        else
        {
            dp[node].first=min({v1, dp[e.first].first,dp[node].first});
            dp[node].second=min({v2,dp[e.first].second,dp[node].second});
        }
        // ans=min(ans, min(dp[e.first].first,curm.first)+min(dp[e.first].second,curm.second));
        dbg(ans);
        dbg(dp[e.first].first);
        dbg(dp[e.first].second);
        dbg(curm.first);
        dbg(curm.second);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    // cin>>t;
    t=1;
    while(t--)
    {
        ll n, m;
        cin>>n>>m;
        ll s, t, u, v;
        cin>>s>>t>>u>>v;
        vector<vector<pair<ll,ll>>> adj(n);
        dp.assign(n,{-1,-1});
        s--;t--;u--;v--;
        for (int i=0;i<m;i++)
        {
            ll x,y,c;
            cin>>x>>y>>c;
            x--;y--;
            adj[x].push_back({y,c});
            adj[y].push_back({x,c});
        }
        ud=dijkstra(adj,u,n);
        sd=dijkstra(adj,s,n);
        td=dijkstra(adj,t,n);
        vd=dijkstra(adj,v,n);
        ans=ud[v];
        ll val1=ud[s];
        ll val2=vd[s];
        ll l3iba=sd[t];
        dp[t]={ud[t],vd[t]};
        dfs(s,adj,0,{val1,val2},l3iba,t);
        cout << ans << endl;
    }
}

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