Submission #518497

#	Time	Username	Problem	Language	Result	Execution time	Memory
518497		vijay	Commuter Pass (JOI18_commuter_pass)	C++17	39 / 100	720 ms	35104 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <string>
#include <climits>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <assert.h>
using namespace std;

using ll = long long;
#define pb push_back
#define mp make_pair

int n, m, s, t, u, v;
vector<vector<pair<int, int> > > adj; // cost first, then position

vector<int> dist(int start, vector<vector<pair<int, int> > > adj){
  vector<int> ret(n, -1);
  priority_queue<pair<ll, pair<int, int> >, vector<pair<ll, pair<int, int> > >, greater<pair<ll, pair<int, int> > > > pq;
  pq.push(mp(0, mp(start, -1)));
  while(!pq.empty()){
    pair<ll, pair<int, int> > curr = pq.top(); pq.pop();
    if(ret[curr.second.first] != -1){
      continue;
    }
    ret[curr.second.first] = curr.first;

    for(auto& edge: adj[curr.second.first]){
      pq.push(mp(edge.first + curr.first, mp(edge.second, curr.second.first)));
    }
  }
  return ret;
}

vector<int> prev(int start, vector<vector<pair<int, int> > > adj){
  vector<int> ret(n, -1);
  priority_queue<pair<ll, pair<int, int> >, vector<pair<ll, pair<int, int> > >, greater<pair<ll, pair<int, int> > > > pq;
  pq.push(mp(0, mp(start, -1)));
  while(!pq.empty()){
    pair<ll, pair<int, int> > curr = pq.top(); pq.pop();
    if(ret[curr.second.first] != -1){
      continue;
    }
    ret[curr.second.first] = curr.second.second;

    for(auto& edge: adj[curr.second.first]){
      pq.push(mp(edge.first + curr.first, mp(edge.second, curr.second.first)));
    }
  }
  return ret;
}


int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  // ifstream cin;
  // cin.open("test.in");

  cin >> n >> m >> s >> t >> u >> v;
  adj.resize(n);
  for(int i = 0; i < m; i++){
    int a, b, c; cin >> a >> b >> c; a--; b--;
    adj[a].pb(mp(c, b));
    adj[b].pb(mp(c, a));
  }
  s--; t--; u--; v--;

  // figure out, with the option to have gone on the train
  vector<int> sdist = dist(s, adj);
  vector<int> sprev = prev(s, adj);
  vector<int> tdist = dist(t, adj);
  vector<int> tprev = prev(t, adj);

  // cout << "sdist: ";
  // for(int i = 0; i < n; i++){
  //   cout << sdist[i] << " ";
  // }
  // cout << "\n";
  //
  // cout << "tdist: ";
  // for(int i = 0; i < n; i++){
  //   cout << tdist[i] << " ";
  // }
  // cout << "\n";

  vector<vector<bool> > visited(n, vector<bool>(4, false));
  // 0 - haven't done it
  // 1 - doing it
  // 2 - already done it

  priority_queue<pair<ll, pair<int, int> >, vector<pair<ll, pair<int, int> > >, greater<pair<ll, pair<int, int> > > > pq; // <distance, <pos, 0-1-2> >
  pq.push(mp(0, mp(u, 0)));

  while(!pq.empty()){
    pair<ll, pair<int, int> > curr = pq.top(); pq.pop();
    if(visited[curr.second.first][curr.second.second]){
      continue;
    }
    visited[curr.second.first][curr.second.second] = true;

    // cout << "minimum distance " << (curr.second.first + 1) << " " << curr.second.second << " " << " is " << curr.first << "\n";

    if(curr.second.first == v){
      cout << curr.first << "\n";
      return 0;
    }


    for(auto& edge: adj[curr.second.first]){
      bool isOnPath = (edge.first + sdist[edge.second] + tdist[curr.second.first]) == sdist[t] || (edge.first + sdist[curr.second.first] + tdist[edge.second] == tdist[s]);
      if(curr.second.second == 0){ // haven't started
        if(isOnPath && tdist[edge.second] < tdist[curr.second.first]){
          pq.push(mp(curr.first, mp(edge.second, 1)));
        }
        if(isOnPath && sdist[edge.second] < sdist[curr.second.first]){
          pq.push(mp(curr.first, mp(edge.second, 2)));
        }
        pq.push(mp(curr.first + edge.first, mp(edge.second, 0)));
      } else if (curr.second.second == 1){ // moving to t
        if(isOnPath && tdist[edge.second] < tdist[curr.second.first]){
          pq.push(mp(curr.first, mp(edge.second, 1)));
        } else {
          pq.push(mp(curr.first + edge.first, mp(edge.second, 3)));
        }
      } else if (curr.second.second == 2){ // moving to s
        // is the distance from
        if(isOnPath && sdist[edge.second] < sdist[curr.second.first]){
          pq.push(mp(curr.first, mp(edge.second, 2)));
        } else {
          pq.push(mp(curr.first + edge.first, mp(edge.second, 3)));
        }
      } else { // done
        pq.push(mp(curr.first + edge.first, mp(edge.second, 3)));
      }
    }
  }
}

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