Submission #1010009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010009		kebine	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	502 ms	56160 KiB

commuter_pass

#include<bits/stdc++.h>
#define int long long
#define pu push_back
#define pii pair<int, int>
#define pipi pair<pii, pii> 
#define pu push_back
#define fi first
#define se second

using namespace std;
const int maxn = 1e5;
const int inf = 1e15;

int n, m, s, t, u, v;
int ds[maxn+5], dt[maxn+5], dp[4][maxn+5];
vector<pii> adj[maxn+5];
priority_queue<pii, vector<pii>, greater<pii>> q;
priority_queue<pipi, vector<pipi>, greater<pipi>> p;
map<pii, int> edge;

signed main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> m >> s >> t >> u >> v;
  for (int i=1; i<=m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].pu({b, c});
    adj[b].pu({a, c});
    edge[{a, b}] = c;
    edge[{b, a}] = c;
  }
  
  for (int i=0; i<=n; i++) {
    ds[i] = dt[i] = inf;
    for (int j=0; j<4; j++) dp[j][i] = inf;
  }

  // do the same for nodes s and t
  ds[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int now = q.top().se, dis = q.top().fi; q.pop();
    if (dis > ds[now]) continue;
    for (auto i: adj[now]) {
      if (dis + i.se >= ds[i.fi]) continue;
      ds[i.fi] = dis + i.se;
      q.push({ds[i.fi], i.fi});
    }    
  }
  dt[t] = 0;
  q.push({0, t});
  while (!q.empty()) {
    int now = q.top().se, dis = q.top().fi; q.pop();
    if (dis > dt[now]) continue;
    for (auto i: adj[now]) {
      if (dis + i.se >= dt[i.fi]) continue;
      dt[i.fi] = dis + i.se;
      q.push({dt[i.fi], i.fi});
    }    
  }
  
  // dis, state, current node, previous node
  p.push({{0, 0}, {u, -1}});
  dp[0][u] = 0;
  while (!p.empty()) {
    int now = p.top().se.fi, dis = p.top().fi.fi, state = p.top().fi.se, bef = p.top().se.se; p.pop();
    if (state == 0) {
      for (auto i: adj[now]) {
        if (i.se + ds[now] + dt[i.fi] == ds[t]) {// next node is on the shortest path
          if (dp[state][now] >= dp[1][i.fi]) continue;
          dp[1][i.fi] = dp[state][now];
          p.push({{dp[1][i.fi], 1}, {i.fi, now}});
        }
      }
      for (auto i: adj[now]) {
        if (i.se + dt[now] + ds[i.fi] == ds[t]) {// next node is on the shortest path
          if (dp[state][now] >= dp[2][i.fi]) continue;
          dp[2][i.fi] = dp[state][now];
          p.push({{dp[2][i.fi], 2}, {i.fi, now}});
        }
      }
      for (auto i: adj[now]) {
        if (dp[state][now] + i.se >= dp[0][i.fi]) continue;
        dp[0][i.fi] = dp[state][now] + i.se;
        p.push({{dp[0][i.fi], 0}, {i.fi, now}});
      }
    }
    if (state == 1) {
      for (auto i: adj[now]) {
        if (i.se + ds[now] + dt[i.fi] == ds[t]) { // next node is on the shortest path
          if (dp[state][now] >= dp[1][i.fi]) continue;
          dp[1][i.fi] = dp[state][now];
          p.push({{dp[1][i.fi], 1}, {i.fi, now}});
        }
        else {
          if (dp[state][now] + i.se >= dp[3][i.fi]) continue;
          dp[3][i.fi] = dp[state][now] + i.se;
          p.push({{dp[3][i.fi], 3}, {i.fi, now}});
        }
      }
    }
    if (state == 2) {
      for (auto i: adj[now]) {
        if (i.se + dt[now] + ds[i.fi] == ds[t]) { // next node is on the shortest path
          if (dp[state][now] >= dp[2][i.fi]) continue;
          dp[2][i.fi] = dp[state][now];
          p.push({{dp[2][i.fi], 2}, {i.fi, now}});
        }
        else {
          if (dp[state][now] + i.se >= dp[3][i.fi]) continue;
          dp[3][i.fi] = dp[state][now] + i.se;
          p.push({{dp[3][i.fi], 3}, {i.fi, now}});
        }
      }
    }
    if (state == 3) {
      for (auto i: adj[now]) {
        if (dp[state][now] + i.se >= dp[3][i.fi]) continue;
        dp[3][i.fi] = dp[state][now] + i.se;
        p.push({{dp[3][i.fi], 3}, {i.fi, now}});
      }
    }
  }
  
  int ans = inf;
  for (int i=0; i<4; i++) {
    ans = min(ans, dp[i][v]);
  }
  cout << ans << endl;
  return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:66:30: warning: unused variable 'dis' [-Wunused-variable]
   66 |     int now = p.top().se.fi, dis = p.top().fi.fi, state = p.top().fi.se, bef = p.top().se.se; p.pop();
      |                              ^~~
commuter_pass.cpp:66:74: warning: unused variable 'bef' [-Wunused-variable]
   66 |     int now = p.top().se.fi, dis = p.top().fi.fi, state = p.top().fi.se, bef = p.top().se.se; p.pop();
      |                                                                          ^~~

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