Submission #976247

#	Time	Username	Problem	Language	Result	Execution time	Memory
976247		UltraFalcon	Robot (JOI21_ho_t4)	C++17	100 / 100	522 ms	63904 KiB

Main

#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,mmx,fma,popcnt")
#endif

#include <bits/stdc++.h>
#define int long long
using ll = long long;

using namespace std;

const int INF = 1e18;

int n, m;
vector<vector<array<int, 3>>> adj;
vector<map<int, int>> cost_sum;

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

    cin >> n >> m;

    adj.assign(n, {});
    cost_sum.assign(n, {});
    for (int i=0; i<m; i++) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        a--; b--;
        adj[a].push_back({b, c, p});
        adj[b].push_back({a, c, p});
        cost_sum[a][c] += p;
        cost_sum[b][c] += p;
    }

    priority_queue<pair<int, int>,
                   vector<pair<int, int>>,
                   greater<pair<int, int>>> pq;
    vector<int> dist(n, INF);
    vector<map<int, int>> min_cost_col(n);

    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();
        if (dist[v] < INF) continue;
        dist[v] = d;
        for (auto [u, c, p] : adj[v]) { 
            if (dist[u] < INF) continue;
            if (cost_sum[v][c] == p) {
                // only one edge of color c
                pq.push({d, u});
            } else {
                pq.push({d+p, u});
                if (min_cost_col[u].count(c) == 0) min_cost_col[u][c] = INF;
                min_cost_col[u][c] = min(min_cost_col[u][c], d);
                pq.push({d + cost_sum[v][c]-p, u});
                // Case 2
                if (min_cost_col[v].count(c) == 0) min_cost_col[v][c] = INF;
                pq.push({min_cost_col[v][c]+cost_sum[v][c]-p, u});
            }
        }
    }

    if (dist[n-1] >= INF) {
        cout << -1 << "\n";
        return 0;
    }
    cout << dist[n-1] << "\n";


}

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