Submission #996637

#	Time	Username	Problem	Language	Result	Execution time	Memory
996637		Marszpace	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	297 ms	36352 KiB

commuter_pass

/*
 * With a little appreciation, in a mostly hollow tone, she says, "Delightful." As if the world has any meaning.
 * TASK : Commuter Pass
 * AUTHOR : Marszpace
*/

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define t5i tuple<int,int,int,int,int>

int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n,m,s,t,u,v;
  cin >> n >> m >> s >> t >> u >> v;

  vector<vector<pii>> edges(n+1,vector<pii>());
  for(int i=0;i<m;i++){
    int a,b,c;
    cin >> a >> b >> c;
    edges[a].push_back({c,b});
    edges[b].push_back({c,a});
  }

  vector<int> distfromu(n+1,LLONG_MAX), distfromv(n+1,LLONG_MAX), distfin(n+1,LLONG_MAX);
  
  {
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  pq.push({0,u});
  while(!pq.empty()){
    auto [d,a]=pq.top();pq.pop();
    if(distfromu[a]!=LLONG_MAX){continue;}
    distfromu[a]=d;
    for(auto [c,b]:edges[a]){
      pq.push({d+c,b});
    }
  }

  pq.push({0,v});
  while(!pq.empty()){
    auto [d,a]=pq.top();pq.pop();
    if(distfromv[a]!=LLONG_MAX){continue;}
    distfromv[a]=d;
    for(auto [c,b]:edges[a]){
      pq.push({d+c,b});
    }
  }
  }
  
  priority_queue<t5i, vector<t5i>, greater<t5i>> pq;

  pq.push({0, distfromv[s]+distfromu[s], distfromv[s], distfromu[s], s});

  while(!pq.empty()){
    auto [d,ans,ans1,ans2,a]=pq.top();pq.pop();
    if(distfin[a]!=LLONG_MAX){continue;}
    distfin[a]=ans;
    for(auto [c,b]:edges[a]){
      pq.push({d+c, 
          min(ans1,distfromv[b])+min(ans2,distfromu[b]), 
          min(ans1,distfromv[b]), 
          min(ans2,distfromu[b]),
          b});
    }
  }
  cout << min(distfromu[v],distfin[t]);
  return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:32:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     auto [d,a]=pq.top();pq.pop();
      |          ^
commuter_pass.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for(auto [c,b]:edges[a]){
      |              ^
commuter_pass.cpp:42:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     auto [d,a]=pq.top();pq.pop();
      |          ^
commuter_pass.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for(auto [c,b]:edges[a]){
      |              ^
commuter_pass.cpp:56:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     auto [d,ans,ans1,ans2,a]=pq.top();pq.pop();
      |          ^
commuter_pass.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [c,b]:edges[a]){
      |              ^

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