Submission #1009099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009099		devariaota	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2011 ms	31172 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 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, ans = inf;
int dist[maxn+5], a[maxn+5], b[maxn+5], c[maxn+5];
map<pii, int> edge;
vector<int> adj[maxn+5], pre[maxn+5];
vector<int> path;
pri<pii, vector<pii>, greater<pii>> pq;

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;
}

void brute_force(int cur) {
  if (cur == s) {
    // clean the halls
    for (int i=0; i<path.size()-1; i++) {
      if (debug) cout << path[i] << " -> ";
      upd(path[i], path[i+1], 0);
    }
    if (debug) cout << endl;
    
    // dijkstra
    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 (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});
      } 
    }    
    
    ans = min(ans, dist[v]);
    
    for (int i=1; i<=m; i++) upd(a[i], b[i], c[i]);
    return;
  }
  for (int p: pre[cur]) {
    path.push_back(p);
    brute_force(p);
    path.pop_back();
  }
}

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++)  {
    cin >> a[i] >> b[i] >> c[i];
    adj[a[i]].push_back(b[i]);
    adj[b[i]].push_back(a[i]);
    upd(a[i], b[i], c[i]);
  }
  

  for (int i=1; i<=n; i++) dist[i] = inf;
  pq.push({0, s});
  dist[s] = 0;
  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;
      if (dis + len(now, nxt) == dist[nxt]) {
        pre[nxt].push_back(now);
        continue;
      }
      dist[nxt] = dis + len(now, nxt);
      pre[nxt].clear();
      pre[nxt].push_back(now);
      pq.push({dist[nxt], nxt});
    } 
  }
  
  if (n <= 300) {
    brute_force(t);
    cout << ans << endl;    
  }

  return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void brute_force(long long int)':
commuter_pass.cpp:37:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=0; i<path.size()-1; i++) {
      |                   ~^~~~~~~~~~~~~~

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