Submission #1253240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253240		escobrand	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	248 ms	19108 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define mk make_pair
typedef pair<ll,ll> pii;
int i,n,t,m,u,v;
const int maxn = 1e5 +10;
vector<pii> adj[maxn];
int source[4];
priority_queue<pii,vector<pii>,greater<>>q;
ll d[4][maxn];
ll mn[4][maxn],w,ans;

void dik(int id)
{
  for(i = 1;i<=n;i++)d[id][i] = LLONG_MAX;
  i = source[id];
  d[id][i] = 0;
  q.push({0,i});
  while(q.size())
  {
    i = q.top().se;
    w = q.top().fi;
    q.pop();
    // cout<<id<<' '<<i<<'\n';
    if(w != d[id][i])continue;
    for(pii k : adj[i])
    {
      if(d[id][k.fi]>w + k.se)
      {
        d[id][k.fi]=w + k.se;
        q.push({d[id][k.fi],k.fi});
      }
    }
  }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m;
    for(i = 0;i<4;i++)cin>>source[i];
    while(m--)
    {
      cin>>u>>v>>w;
      adj[u].pb({v,w});
      adj[v].pb({u,w});
    }
    for(int i = 1;i<4;i++)dik(i);
    ans = d[2][source[3]];
    for(i = 1;i<=n;i++)
    {
      d[0][i] = mn[2][i] = mn[3][i] = LLONG_MAX;
    }
    i = source[0];
    d[0][i] = 0;
    q.push({0,i});
    while(q.size())
    {
      i = q.top().se;
      w = q.top().fi;
      q.pop();
      if(w != d[0][i])continue;
      mn[2][i] = min(mn[2][i],d[2][i]);
      mn[3][i] = min(mn[3][i],d[3][i]);
      
      if(d[1][i] + w == d[1][source[0]])
      {
        ans = min({ans,mn[2][i] + d[3][i],mn[3][i] + d[2][i]});
      }
      
      for(pii k : adj[i])
      {
        if(d[0][k.fi]>w + k.se)
        {
          d[0][k.fi]= w + k.se;
          q.push({d[0][k.fi],k.fi});
          mn[2][k.fi] = mn[2][i];
          mn[3][k.fi] = mn[3][i];
        }
        else if(d[0][k.fi]==w + k.se)
        {
          mn[2][k.fi] = min(mn[2][k.fi],mn[2][i]);
          mn[3][k.fi] = min(mn[3][k.fi],mn[3][i]);
        }
      }
    }
    cout<<ans;
    
    return 0;
}

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