Submission #1265322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265322		quangan1612008	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	209 ms	16864 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define i32 int32_t
#define ll long long
#define el '\n'
#define pb push_back
#define fi first
#define se second
#define BIT(x , i) (((x) >> (i)) & 1)

const int mod = 1e9 + 7;
const int inf = 1e9;
const ll lnf = 1e16;
const int mxN = 1e5;

int n , m , s , t , u , v;
ll ds[100005] , dt[100005] , du[100005] , dv[100005] , dpU[2][100005] , dpV[2][100005];
bool vis[100005];
vector < pair < int , int >> adj[100005];
vector < int > dag;

void dijkstra(int i, ll d[]) {
  priority_queue< pair < ll , ll > , vector < pair < ll , ll >> , greater < pair < ll , ll >>> pq;
  fill(d, d + n + 1, lnf);
  d[i] = 0;
  pq.push({0, i});
  while (!pq.empty()) {
    ll dist , u; tie(dist , u) = pq.top();
    pq.pop();
    if (dist != d[u]) continue;
    for (auto i : adj[u]) {
      int v , w; tie(v , w) = i;
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        pq.push({d[v], v});
      }
    }
  }
}

/*
  dag tạo bởi shortest path từ s -> t
  i thuộc dag <=> ds[i] + dt[i] = ds[t] , sort dag theo ds[i] , khi đó tạo ra thứ tự topo trong dag


  dpU[x] : mincost để đi từ u đến các đỉnh v với v <= x trên dag
  khởi tạo : dpU[i] = du[i]
  dpU[i] = min(dpU[i] , dpU[par[i]])
  reverse dag và làm lại với dpV
  res = min(res , dpU[i] + dpV[i]);

  path : dist(u , x) + dist(y , v);
*/

void solve() {
  cin >> n >> m >> s >> t >> u >> v;
  for(int i = 1 ; i <= m ; i++){
    int u , v , w;
    cin >> u >> v >> w;
    adj[u].push_back({v , w});
    adj[v].push_back({u , w});
  }
  dijkstra(s , ds);
  dijkstra(t , dt);
  dijkstra(u , du);
  dijkstra(v , dv);
  for(int i = 1 ; i <= n ; i++){
    if(ds[i] + dt[i] == ds[t]) {
      dag.push_back(i);
    }
  }
  sort(dag.begin() , dag.end() , [&](int x , int y) {
    return ds[x] < ds[y];
  });
  for(auto i : dag) {
    dpU[0][i] = dpU[1][i] = du[i];
    dpV[0][i] = dpV[1][i] = dv[i];
  }
  memset(vis , 0 , sizeof vis);
  for(int x : dag) {
    vis[x] = 1;
    for(auto i : adj[x]) {
      int y = i.first;
      if(ds[y] + dt[y] != ds[t] || vis[y]) continue;
      dpU[0][y] = min(dpU[0][y] , dpU[0][x]);
    }
  }
  memset(vis , 0 , sizeof vis);
  for(int x : dag) {
    vis[x] = 1;
    for(auto i : adj[x]) {
      int y = i.first;
      if(ds[y] + dt[y] != ds[t] || vis[y]) continue;
      dpV[0][y] = min(dpV[0][y] , dpV[0][x]);
    }
  }
  ll res = du[v];
  memset(vis , 0 , sizeof vis);
  for(int x : dag) {
    vis[x] = 1;
    for(auto i : adj[x]) {
      int y = i.first;
      if(ds[y] + dt[y] != ds[t] || vis[y]) continue;
      dpU[1][y] = min(dpU[1][y] , dpU[1][x]);
    }
    res = min(res , dpV[0][x] + dpU[1][x]);
  }
  memset(vis , 0 , sizeof vis);
  for(int x : dag) {
    vis[x] = 1;
    for(auto i : adj[x]) {
      int y = i.first;
      if(ds[y] + dt[y] != ds[t] || vis[y]) continue;
      dpV[1][y] = min(dpV[1][y] , dpV[1][x]);
    }
    res = min(res , dpU[0][x] + dpV[1][x]);
  }
  cout << res << el;
}

i32 main()
{
#define TASKNAME "daisy"
  if (fopen(TASKNAME ".inp", "r")) {
    freopen(TASKNAME ".inp", "r", stdin);
    freopen(TASKNAME ".out", "w", stdout);
  }
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int testcase = 1;
  while (testcase--){
    solve();
  }
  return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     freopen(TASKNAME ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     freopen(TASKNAME ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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