Submission #535754

#	Time	Username	Problem	Language	Result	Execution time	Memory
535754		sam571128	Robot (JOI21_ho_t4)	C++17	0 / 100	135 ms	21800 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e5+5, M = 2e5 + 5;
struct edge {
    int v, c, p;
};

int dis[N], cnt[M];
vector<edge> adj[N];

signed main() {
    fastio
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        adj[u].push_back({v, c, p});
        adj[v].push_back({u, c, p});

    }

    fill(dis,dis+N,1e18);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    dis[1] = 0;
    pq.push({0, 1});
    //dis, vertex, lst

    while (!pq.empty()) {
        auto [ww, u] = pq.top();
        pq.pop();

        if (ww > dis[u])
            continue;

        for (auto [v, c, p] : adj[u]) {
            cnt[c]++;
        }

        for (auto [v, c, p] : adj[u]) {
            if (dis[v] > dis[u] + (cnt[c] == 1 ? 0 : 1)) {
                dis[v] = dis[u] + (cnt[c] == 1 ? 0 : 1);
                pq.push({dis[v], v});
            }
        }

        for (auto [v, c, p] : adj[u]) {
            cnt[c]--;
        }
    }

    int ans = 1e18;

    ans = min(ans,dis[n]);
    cout << (ans == 1e18 ? -1 : ans) << "\n";
}

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