Submission #74553

#	Time	Username	Problem	Language	Result	Execution time	Memory
74553		garyye	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	401 ms	87376 KiB

commuter_pass

// author: gary
// created: 2018/09/03 13:29:03
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <limits>
#include <utility>
#include <functional>
#include <string>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
#define SZ(x) ( (int) (x).size() )
#define ALL(c) (c).begin(), (c).end()
#define CNT(c, x) ((c).find(x) != (c).end())
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
template<class T> bool cmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool cmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }

const int INF = 1e9;
const int N = 100005;

int n, m, S, T, U, V;

vector<pii> E[N];

ll d[2][N]; // d[U][.] and d[V][.]

void dijkstra(ll* dist, int u) {
  priority_queue<pli, vector<pli>, greater<pli>> pq;
  fill(dist, dist + N, 1LL<<62);
  dist[u] = 0;
  pq.push(mp(0, u));
  while(!pq.empty()) {
    pli t = pq.top();
    pq.pop();
    if(dist[t.second] < t.first) {
      continue;
    }
    for(auto& e: E[t.second]) {
      if(cmin(dist[e.first], t.first + e.second)) {
        pq.push(mp(dist[e.first], e.first));
      }
    }
  }
}

ll dist[N];
ll min_d[2][N];
ll min_sum[N];

ll calc(int U, int V) {
  priority_queue<pli, vector<pli>, greater<pli>> pq;
  fill(dist, dist + N, 1LL<<62);
  fill(min_sum, min_sum + N, 1LL<<62);
  for(int i = 1; i <= n; i++) {
    min_sum[i] = 1LL<<62;
    min_d[0][i] = min_d[1][i] = 1LL<<62;
  }
  dist[U] = 0;
  min_sum[U] = d[0][U] + d[1][U];
  min_d[0][U] = d[0][U];
  min_d[1][U] = d[1][U];

  pq.push(mp(0LL, U));
  while(!pq.empty()) {
    pli t = pq.top();
    pq.pop();
    int u = t.second;
    ll cost = t.first;
    if(dist[u] < cost) {
      continue;
    }
    for(auto& e: E[u]) {
      int v = e.first;
      ll ndist = cost + e.second;
      
      if(dist[v] < ndist) {
        continue;
      }
      if(dist[v] > ndist) {
        for(int i = 0; i < 2; i++) {
          min_d[i][v] = d[i][v];
        }
        min_sum[v] = 1LL << 62;
        dist[v] = ndist;
        pq.push(mp(dist[v], v));
      }
      for(int i = 0; i < 2; i++) {
        cmin(min_d[i][v], min_d[i][u]);
      }

      cmin(min_sum[v], min_d[0][v] + d[1][v]);
      cmin(min_sum[v], min_d[1][v] + d[0][v]);

      cmin(min_sum[v], min_sum[u]);
    }
  }
  /*
  for(int i = 1; i <= n; i++) {
    printf("min_sum: %d %lld\n", i, min_sum[i]);
  }
  */
  return min_sum[V];
}

int main() {
  cin >> n >> m >> S >> T >> U >> V;
  for(int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    E[u].emplace_back(v, w);
    E[v].emplace_back(u, w);
  }

  dijkstra(d[0], U);
  dijkstra(d[1], V);
  // for(int i = 1; i <= n; i++) { printf("%lld %lld\n", d[0][i], d[1][i]); }
  printf("%lld\n", min(d[0][V], calc(S, T)));
  return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &u, &v, &w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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