Submission #1112264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112264		polarity	Robot (JOI21_ho_t4)	C++17	0 / 100	193 ms	13128 KiB

Main

/**
 * Solution by 1egend (polarity.sh)
 * Date: 2024-11-13
 * Contest: CSES Problemset - Graph Algorithms
 * Problem: 1202
**/

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ull unsigned long long
#define ll long long

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;

void solve(){
    int n, m; cin >> n >> m;

    vector<ll> dist(n, 1e15);
    map<pair<int, int>, vector<pair<int, int>>> multiple;
    vector<vector<tuple<int, int, ll>>> adj(n);
    for (int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c;
        --a; --b; --c;
        ll d; cin >> d;

        if (multiple[{a, c}].size() < 3){
            multiple[{a, c}].pb({b, d});
        }

        if (multiple[{b, c}].size() < 3){
            multiple[{b, c}].pb({a, d});
        }

        adj[a].pb({b, c, d});
        adj[b].pb({a, c, d});
    }

    using T = tuple<ll, int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;

    dist[0] = 0;
    pq.push({0LL, 0, -1});

    while(!pq.empty()){
        auto [ndist, k, c] = pq.top();
        pq.pop();

        if (ndist != dist[k]) { continue; }

        for (tuple<int, int, ll> &node: adj[k]){
            int kk = get<0>(node);
            int color = get<1>(node);
            ll cost = get<2>(node);
            if (multiple[{k, color}].size() == 1 || multiple[{k, color}].size() == 2 && c == color){
                cost = 0;
            }

            if (ndist + cost < dist[kk]){
                dist[kk] = ndist + cost;
                pq.push({dist[kk], kk, color});
            }
            
            else if (multiple[{kk, color}].size() == 2){
                int t = multiple[{kk, color}][0].first;
                if (t == k){
                    t = multiple[{kk, color}][1].first;
                }
                if (ndist + get<2>(node) < dist[t]){
                    dist[t] = ndist + get<2>(node);
                    pq.push({dist[t], t, color});
                }
            }
        }
    }

    cout << (dist[n - 1] == 1e15 ? -1: dist[n - 1])<< endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:57:86: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   57 |             if (multiple[{k, color}].size() == 1 || multiple[{k, color}].size() == 2 && c == color){
      |                                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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