Submission #666264

#	Time	Username	Problem	Language	Result	Execution time	Memory
666264		chanhchuong123	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	346 ms	20388 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}

const long long INF = 1e18;
const int N = 1e5 + 4;
int n, m;
int S, T;
int U, V;
long long d[N][4];
long long dp[N][2];
vector<pair<int, int>> adj[N];

void Dijkstra(int s, int type) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    for (int i = 1; i <= n; i++) d[i][type] = INF; pq.push(make_pair(0, s)); d[s][type] = 0;
    while (pq.size()) {
        long long du = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if (du != d[u][type]) continue;

        for (pair<int, int> x: adj[u]) {
            int v = x.fi, w = x.se;
            if (mini(d[v][type], du + w))
                pq.push(make_pair(d[v][type], v));
        }
    }
}

main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  if (fopen(task".inp","r")) {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

    cin >> n >> m;
    cin >> S >> T;
    cin >> U >> V;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
    Dijkstra(S, 0); Dijkstra(T, 1);
    Dijkstra(U, 2); Dijkstra(V, 3);

    for (int i = 1; i <= n; i++)
        dp[i][0] = dp[i][1] = INF;

    // calc array dp[_][__]
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    for (int i = 1; i <= n; i++) {
        if (d[i][0] + d[i][1] == d[T][0])
            pq.push(make_pair(d[i][0], i));
    }
    while (pq.size()) {
        long long du = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        mini(dp[u][0], d[u][2]);
        mini(dp[u][1], d[u][3]);
        for (pair<int, int> x: adj[u]) {
            int v = x.fi, w = x.se;
            if (du + w + d[v][1] == d[T][0]) {
                mini(dp[v][0], dp[u][0]);
                mini(dp[v][1], dp[u][1]);
            }
        }
    }
    long long ans = d[V][2];
    for (int i = 1; i <= n; i++) {
        if (d[i][0] + d[i][1] == d[T][0]) {
            mini(ans, dp[i][0] + d[i][3]);
            mini(ans, dp[i][1] + d[i][2]);
        }
    }
    cout << ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void Dijkstra(int, int)':
commuter_pass.cpp:27:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   27 |     for (int i = 1; i <= n; i++) d[i][type] = INF; pq.push(make_pair(0, s)); d[s][type] = 0;
      |     ^~~
commuter_pass.cpp:27:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   27 |     for (int i = 1; i <= n; i++) d[i][type] = INF; pq.push(make_pair(0, s)); d[s][type] = 0;
      |                                                    ^~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main() {
      | ^~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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