Submission #1143536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143536		poltanos	Robot (JOI21_ho_t4)	C++20	0 / 100	244 ms	51972 KiB

Main

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

const int inf = 1e18;

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

    vector<vector<pair<int, int>>> adj(n); // { adj_node, cost }
    vector<multiset<int>> deg_col(n);
    vector<vector<int>> edges(m); // {x, y, wt, col}
    for(int i = 0; i < m; i++){
        int x, y, col, wt;
        cin >> x >> y >> col >> wt;
        x--, y--;

        deg_col[x].insert(col);
        deg_col[y].insert(col);

        edges[i] = {x, y, wt, col};
    }

    for(auto edge : edges){
        int x = edge[0], y = edge[1], wt = edge[2], col = edge[3];

        if(deg_col[x].count(col) == 1) adj[x].push_back({y, 0});
        else adj[x].push_back({y, wt});

        if(deg_col[y].count(col) == 1) adj[y].push_back({x, 0});
        else adj[y].push_back({x, wt});
    }

    vector<int> dist(n, inf);
    vector<int> processed(n, false);
    dist[0] = 0;

    priority_queue<pair<int, int>> q;
    q.push({0, 0});

    while(!q.empty()){
        int a = q.top().second;
        q.pop();

        if(processed[a]) continue;
        processed[a] = true;

        for(auto [b, wt] : adj[a]){
            if(dist[a] + wt < dist[b]){
                dist[b] = dist[a] + wt;
                q.push({-dist[b], b});
            }
        }
    }

    if(dist[n - 1] == inf){
        cout << -1 << endl;
        return;
    }

    cout << dist[n - 1] << endl;
}

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

    int t = 1;
    while(t--) solve();

    return 0;
}

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