Submission #1005971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005971		c2zi6	Robot (JOI21_ho_t4)	C++14	100 / 100	1243 ms	107000 KiB

Main

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct EDGE {
    int u, v, c, w;
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<EDGE> edges(m);
    vector<map<int, ll>> sum(n);
    vector<map<int, VPI>> gp(n);
    for (auto&[u, v, c, w] : edges) {
        cin >> u >> v >> c >> w;
        u--, v--;
        gp[u][c].pb({v, w});
        gp[v][c].pb({u, w});
        sum[u][c] += w;
        sum[v][c] += w;
    }
    priority_queue<pair<ll, PII>> pq;
    /*distance, {node, prev color}*/
    map<PII, ll> dist;
    map<PII, bool> vis;
    pq.push({0, {0, 0}});
    dist[{0, 0}] = 0;
    while (pq.size()) {
        int u, c;
        tie(u, c) = pq.top().ss;
        pq.pop();
        if (vis[{u, c}]) continue;
        vis[{u, c}] = true;
        if (c == 0) {
            for (auto& P : gp[u]) {
                int c = P.ff;
                for (auto[v, w] : P.ss) {
                    ll case1 = dist[{u, 0}] + min(1ll*w, sum[u][c] - w);
                    if (!dist.count({v, 0}) || case1 < dist[{v, 0}]) {
                        dist[{v, 0}] = case1;
                        pq.push({-dist[{v, 0}], {v, 0}});
                    }
                    ll case2 = dist[{u, 0}];
                    if (!dist.count({v, c}) || case2 < dist[{v, c}]) {
                        dist[{v, c}] = case2;
                        pq.push({-dist[{v, c}], {v, c}});
                    }
                }
            }
        } else {
            for (auto[v, w] : gp[u][c]) {
                ll case3 = dist[{u, c}] + sum[u][c] - w;
                if (!dist.count({v, 0}) || case3 < dist[{v, 0}]) {
                    dist[{v, 0}] = case3;
                    pq.push({-dist[{v, 0}], {v, 0}});
                }
            }
        }
    }
    if (dist.count({n-1, 0})) cout << dist[{n-1, 0}] << endl;
    else cout << -1 << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    /*cin >> t;*/
    while (t--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:43:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for (auto&[u, v, c, w] : edges) {
      |               ^
Main.cpp:66:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |                 for (auto[v, w] : P.ss) {
      |                          ^
Main.cpp:80:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |             for (auto[v, w] : gp[u][c]) {
      |                      ^

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