Submission #1216950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216950		escobrand	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	262 ms	19484 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb push_back
#define ll long long 
#define fi first
#define se second
int t,n,i,j,m,v,w,u;
const int maxn = 1e5 + 10;
const ll inf = 1e15;
typedef pair<ll,ll> pii;
vector<pii>adj[maxn];
int pos[4],c[maxn];
ll from[4][maxn],min2[maxn],min3[maxn],ans;

priority_queue<pii,vector<pii>,greater<>>q;

void dik(int id)
{
  int s = pos[id];
  for(int i = 1;i<=n;i++)from[id][i] = inf;
  from[id][s] = 0;
  q.push({0,s});
  ++t;
  while(q.size())
  {
    s = q.top().se;
    ll val = q.top().fi;
    q.pop();
    if(c[s] == t)continue;
    c[s] = t;
    for(auto k : adj[s])
    {
      if(from[id][k.fi] > val + k.se)
      {
        from[id][k.fi] = val + k.se;
        q.push({val + k.se,k.fi});
      }
    }
  }
}

void solve()
{
  int s = pos[0];
  for(int i = 1;i<=n;i++)from[0][i] = min2[i] = min3[i] = inf;
  from[0][s] = 0;
  q.push({0,s});
  ++t;
  while(q.size())
  {
    int i = q.top().se;
    ll val = q.top().fi;
    q.pop();
    if(c[i] == t)continue;
    c[i] = t;
    min2[i] = min(min2[i],from[2][i]);
    min3[i] = min(min3[i],from[3][i]);
    if(from[1][i] + val == from[1][s])
    {
      // cout<<i<<' ';
      ans = min(ans,min(min2[i] + from[3][i], min3[i] + from[2][i]));
    }
    for(auto k : adj[i])
    {
      if(from[0][k.fi] > val + k.se)
      {
        from[0][k.fi] = val + k.se;
        q.push({val + k.se,k.fi});
        min2[k.fi] = min2[i];
        min3[k.fi] = min3[i];
      }
    }
  }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    for(i = 0;i<4;i++)cin>>pos[i];
    
    while(m--)
    {
      cin>>u>>v>>w;
      adj[u].eb({v,w});
      adj[v].eb({u,w});
    }
    
    for(i = 1;i<4;i++)
    {
      dik(i);
    }
    
    ans = from[2][pos[3]];
    
    solve();
    // cout<<from[0][pos[1]];
    
    cout<<ans;
    
    return 0;
}

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