Submission #632206

#	Time	Username	Problem	Language	Result	Execution time	Memory
632206		Ooops_sorry	Robot (JOI21_ho_t4)	C++14	24 / 100	1136 ms	88868 KiB

Main

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

const ll INF = 1e18, N = 1e5 + 10;
map<int, vector<pair<int,ll>>> g[N];
vector<ll> d(N);
map<int, ll> color_d[N];
map<int, ll> total_sum[N];

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        d[i] = INF;
    }
    for (int i = 0; i < m; i++) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        a--, b--;
        g[a][c].pb({b, p});
        g[b][c].pb({a, p});
        color_d[a][c] = color_d[b][c] = INF;
    }
    for (int v = 0; v < n; v++) {
        for (auto [c, arr] : g[v]) {
            for (auto to : arr) {
                total_sum[v][c] += to.second;
            }
        }
    }
    d[0] = 0;
    //d[v] - минимальный расстояние до вершины с ЛЮБЫМ ребром
    //special_d[v][c] - расстояние до вершины, если последнее ребро было c
    //par[v][c] - индекс ребра, которое было взято последним
    set<array<ll, 4>> st{{0, 0, -1}};
    while (st.size() > 0) {
        auto arr = *st.begin();
        st.erase(st.begin());
        int v = arr[1];
        if (arr[2] == -1) {
            for (auto [c, arr] : g[v]) {
                for (auto [u, p] : arr) {
                    if (d[u] > d[v] + min(total_sum[v][c] - p, p)) {
                        st.erase({d[u], u, -1, -1});
                        d[u] = d[v] + min(total_sum[v][c] - p, p);
                        st.insert({d[u], u, -1, -1});
                    }
                    if (color_d[u][c] > d[v]) {
                        st.erase({color_d[u][c], u, c});
                        color_d[u][c] = d[v];
                        st.insert({color_d[u][c], u, c});
                    }
                }
            }
        } else {
            int c = arr[2];
            for (auto [u, p] : g[v][c]) {
                int dist = color_d[v][c] + total_sum[v][c] - p;
                if (d[u] > dist) {
                    st.erase({d[u], u, -1, -1});
                    d[u] = dist;
                    st.insert({d[u], u, -1, -1});
                }
                if (color_d[u][c] > d[v]) {
                    st.erase({color_d[u][c], u, c});
                    color_d[u][c] = d[v];
                    st.insert({color_d[u][c], u, c});
                }
            }
        }
    }
    cout << (d[n - 1] == INF ? -1 : d[n - 1]) << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         for (auto [c, arr] : g[v]) {
      |                   ^
Main.cpp:53:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |             for (auto [c, arr] : g[v]) {
      |                       ^
Main.cpp:54:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |                 for (auto [u, p] : arr) {
      |                           ^
Main.cpp:69:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |             for (auto [u, p] : g[v][c]) {
      |                       ^

• Subtask 1: 0 / 34
• Subtask 2: 24 / 24
• Subtask 3: 0 / 42