Submission #1008972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008972		andecaandeci	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	564 ms	25352 KiB

commuter_pass

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

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

// Problem B
// Subtask 1: If there are multiple optimal paths from S->T, 
// Subtask 2: There is only one optimal path from S->T, just dijkstra and make the one optimmal path zeroes by keeping track the prev room
// Subtask 3: Possibly brute force 
//         Precompute all optimal paths from S->T, then for each path o(n) dijkstra o(nlogn) > o(n + n^2 logn)

int n, m, s, t, u, v;
int dist[maxn+5], pre[maxn+5];
map<pii, int> edge;
vector<int> adj[maxn+5];

int len(int a, int b) {
  if (a > b) swap(a, b);
  return edge[{a, b}];
}

void upd(int a, int b, int c) {
  if (a > b) swap(a, b);
  edge[{a, b}] = c;
}

signed main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> m;
  cin >> s >> t;
  cin >> u >> v;
  for (int i=1; i<=m; i++)  {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].push_back(b);
    adj[b].push_back(a);
    upd(a, b, c);
  }
  
  // subtask 2
  pri<pii, vector<pii>, greater<pii>> pq;
  for (int i=1; i<=n; i++) dist[i] = inf;
  pq.push({0, s});
  dist[s] = 0;
  pre[s] = -1;
  while (!pq.empty()) {
    int now = pq.top().se, dis = pq.top().fi; pq.pop();
    if (dist[now] < dis) continue;
    for (int nxt: adj[now]) {
      if (dis + len(now, nxt) >= dist[nxt]) continue;
      dist[nxt] = dis + len(now, nxt);
      pre[nxt] = now;
      pq.push({dist[nxt], nxt});
    } 
  }
  if (debug) {
    cout << "pre: " << endl;
    for (int i=1; i<=n; i++) cout << pre[i] << " ";
    cout << endl;    
  }

  int cur = t;
  while (pre[cur] != -1) {
    upd(cur, pre[cur], 0);
    cur = pre[cur];
  }
  for (int i=1; i<=n; i++) dist[i] = inf;
  dist[u] = 0;
  pq.push({0, u});
  while (!pq.empty()) {
    int now = pq.top().se, dis = pq.top().fi; pq.pop();
    if (debug) cout << "now: " << now << " dis: " << dis << endl;
    if (dist[now] < dis) continue;
    for (int nxt: adj[now]) {
      if (dis + len(now, nxt) >= dist[nxt]) continue;
      dist[nxt] = dis + len(now, nxt);
      pq.push({dist[nxt], nxt});
    } 
  }
  if (debug) {
    cout << "dis : " << endl;
    for (int i=1; i<=n; i++) cout << dist[i] << " ";
    cout << endl;    
  }

  cout << dist[v] << endl;
  return 0;
}

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