Submission #1255179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255179		thanhlaihoccode	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	1209 ms	327680 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FILE "task"
#define pb push_back
#define endl '\n'
#define fi first
#define se second
#define ii pair<int, int>
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, l, r) for (int i = l; i >= r; i--)
#define ex exit(0)
#define pf push_front
#define pob pop_back
#define pof pop_front
#define ff fi.fi
//#define fs fi.se
#define ss se.se
#define sf se.fi
#define MASK(i) (1LL << i)
#define BASE 256
int const N = 3e5 + 5, mod = 1e9 + 7, M = 2e6 + 5, K = 34;
int n, m, fx[N], fs[N], fy[N], ft[N], x, y, s, t, ans = 1e18, in[N], flag[N], dp[N];
int mark[N];
vector<ii> e[N];
vector<pair<ii, int>> c;
vector<ii> e2[N];
vector<int> topo;
queue<int> q;
void dijk(int s, int f[N])
{
  FOR(i, 1, n) f[i] = 1e18;
  f[s] = 0;
  priority_queue<ii, vector<ii>, greater<ii>> pq;
  pq.push({0, s});
  
  while(!pq.empty())
  {
    int u = pq.top().se;
    int cost = pq.top().fi;
    pq.pop();
   
    if(cost > f[u]) continue;

    for(auto x : e[u])
    {
      int v = x.fi, w = x.se;
      if(f[v] > f[u] + w)
      {
        f[v] = f[u] + w;
        pq.push({f[v], v});
      }
    }
  }
}

void init()
{
    cin >> n >> m >> s >> t >> x >> y;
    FOR(i, 1, m)
    {
        int x, y, w; cin >> x >> y >> w;
        e[x].pb({y, w});
        e[y].pb({x, w});
        c.pb({{x, y}, w});
    }

    FOR(i, 1, n)
    {
      sort(e[i].begin(), e[i].end());
      e[i].erase(unique(e[i].begin(), e[i].end()), e[i].end());
    }

}

void backtrack(int u)
{
  flag[u]++;
  if(u == s) return;
  for(auto x : e[u])
  {
    int v = x.fi, w = x.se;
    if(fs[u] == fs[v] + w)
    {
      e2[v].pb({u, w});
      in[u]++;
      backtrack(v);
    }
  }
}

void sub2()
{
  if(x == y)
  {
    cout << 0; ex;
  }
    dijk(s, fs);
    dijk(t, ft);

    backtrack(t);
  
    // FOR(i, 1, n)
    // {
    //   for(auto x : e2[i]) cout << i << " " << x.fi << " " << x.se;
    //   cout << endl;
    // }

    int topocnt = 0;
    
    FOR(i, 1, n) if(!in[i] && flag[i] >= 1) q.push(i), mark[i] = ++topocnt;

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        topo.pb(u);
        for(auto x : e2[u])
        {
          int v = x.fi, w = x.se;
            in[v]--;
            if(!in[v]) q.push(v), mark[v] = ++topocnt;
        }
    }

    // for(auto x : topo) cout << x << " ";
    // cout << endl;

    if(mark[x] > mark[y] && mark[x] && mark[y]) swap(x, y);

    dijk(x, fx);
    dijk(y, fy);

    FOR(i, 1, n) dp[i] = 1e18;

    FOD(i, topo.size() - 1, 0)
    {
      int u = topo[i];
      dp[u] = fy[u];
      for(auto x : e2[u])
      {
        int v = x.fi, w = x.se;
        dp[u] = min(dp[u], dp[v]);
      }
    }

    for(auto u : topo)
    {
      ans = min(ans, fx[u] + dp[u]);
  //    cout << fx[u] + dp[u] << " " << fx[u] << " " << dp[u] << endl;
    }

    FOR(i, 1, n) dp[i] = 1e18;

    FOD(i, topo.size() - 1, 0)
    {
      int u = topo[i];
      dp[u] = fx[u];
      for(auto x : e2[u])
      {
        int v = x.fi, w = x.se;
        dp[u] = min(dp[u], dp[v]);
      }
    }

     for(auto u : topo)
    {
      ans = min(ans, fy[u] + dp[u]);
  //    cout << fx[u] + dp[u] << " " << fx[u] << " " << dp[u] << endl;
    }
    cout << min(ans, fx[y]);
}
signed main()
{
if (fopen(FILE ".inp", "r"))
  {
    freopen(FILE ".inp", "r", stdin);
    freopen(FILE ".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
   init();
   sub2();
}

/*
▓████████▓▒░▒▓█▓▒░░▒▓█▓▒░░▒▓██████▓▒░░▒▓███████▓▒░░▒▓█▓▒░░▒▓█▓▒░
 ░▒▓█▓▒░   ░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
 ░▒▓█▓▒░   ░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
 ░▒▓█▓▒░   ░▒▓████████▓▒░▒▓████████▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓████████▓▒░
 ░▒▓█▓▒░   ░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
 ░▒▓█▓▒░   ░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
 ░▒▓█▓▒░   ░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
                                                                 */

Compilation message (stderr)

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

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