Submission #1103543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103543		lmToT27	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	276 ms	24132 KiB

commuter_pass

#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long

using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}

const int MAX = 1e5 + 3;
const ll MOD[] = {1000000007, 998244353};

int n, m, s[4];
vector <int> adj[MAX];
int u[MAX << 1], v[MAX << 1];
ll w[MAX << 1];
ll dp[MAX][4];
typedef ll arr[MAX];
arr d[4];

void dijkstra(int root, arr &dp) {
        memset(dp, 0x0f, sizeof dp);
        dp[root] = 0;
        pair <ll, int> tmp;
        priority_queue <pair <ll, int>> q;
        q.emplace(0, root);
        int u, v;
        ll D, w;
        while (q.size()) {
                tmp = q.top();
                q.pop();
                D = -tmp.first;
                u = tmp.second;
                if (D != dp[u]) continue;
                for (int &i : adj[u]) {
                        v = ::u[i] ^ ::v[i] ^ u;
                        w = ::w[i];
                        if (D + w < dp[v]) {
                                dp[v] = D + w;
                                q.emplace(-dp[v], v);
                        }
                }
        }
}

void Solve() {
        cin >> n >> m;
        for (int i = 3; i >= 0; i--) cin >> s[i];
        for (int i = 1; i <= m; i++) {
                cin >> u[i] >> v[i] >> w[i];
                adj[u[i]].push_back(i);
                adj[v[i]].push_back(i);
        }

        for (int i = 0; i < 4; i++) dijkstra(s[i], d[i]);

        ll ans = d[0][s[1]];

        memset(dp, 0x0f, sizeof dp);
        vector <int> node(n);
        iota(all(node), 1);
        sort(all(node), [&](const int &i, const int &j) {
                return d[2][i] < d[2][j];
        });
        dp[s[2]][0] = 0;
        for (int &u : node) {
                for (int type = 1; type <= 3; type++) {
                        for (int i = 0; i < 2; i++) {
                                if (type >> i & 1) dp[u][type] = min(dp[u][type], dp[u][type ^ (1 << i)] + d[i][u]);
                        }
                }
                for (int &i : adj[u]) {
                        int v = ::u[i] ^ ::v[i] ^ u;
                        ll w = ::w[i];
                        if (d[2][u] + w == d[2][v]) {
                                for (int type = 0; type <= 3; type++) {
                                        dp[v][type] = min(dp[v][type], dp[u][type]);
                                }
                        }
                }
        }

        ans = min(ans, dp[s[3]][3]);
        cout << ans;
}

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

        #define TASK "PATH"
        if (fopen(TASK".INP", "r")) {
                freopen(TASK".INP", "r", stdin);
                freopen(TASK".OUT", "w", stdout);
        }
        
        if (fopen("TASK.INP", "r")) {
                freopen("TASK.INP", "r", stdin);
                freopen("TASK.OUT", "w", stdout);
        }
        
        /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

        cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
        return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:104:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |                 freopen(TASK".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:105:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |                 freopen(TASK".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:109:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:110:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |                 freopen("TASK.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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