Submission #1273232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273232		vk3601h	Robot (JOI21_ho_t4)	C++20	100 / 100	719 ms	79136 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<map<int, vector<tuple<int, int, long long>>>> edges(n);
    vector<map<int, long long>> price_sums(n);
    for (int i = 0; i < m; i++){
        int a, b, c;
        long long p;
        cin >> a >> b >> c >> p;
        a--, b--;

        edges[a][c].push_back({b, c, p});
        edges[b][c].push_back({a, c, p});
        price_sums[a][c] += p;
        price_sums[b][c] += p;
    }

    vector<long long> dist(n, INF);
    vector<map<int, long long>> dist2(n);
    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> frontier;
    dist[0] = 0;
    frontier.push({0, 0, 0});

    while (!frontier.empty()){
        int curr = get<1>(frontier.top());
        int curr_color = get<2>(frontier.top());
        long long curr_dist = get<0>(frontier.top());
        frontier.pop();

        if (curr_color > 0){
            if (dist2[curr][curr_color] != curr_dist) continue;
            for (const auto &edge : edges[curr][curr_color]){
                int node = get<0>(edge);
                long long price = get<2>(edge);

                long long case1 = curr_dist + price_sums[curr][curr_color] - price;
                if (dist[node] > case1){
                    dist[node] = case1;
                    frontier.push({dist[node], node, 0});
                }
            }
        }
        else {
            if (dist[curr] != curr_dist) continue;
            for (const auto &adj : edges[curr]){
                for (const auto &edge : adj.second){
                    int node = get<0>(edge);
                    int color = get<1>(edge);
                    long long price = get<2>(edge);

                    long long case1 = curr_dist + price_sums[curr][color] - price;
                    if (dist[node] > case1){
                        dist[node] = case1;
                        frontier.push({dist[node], node, 0});
                    }

                    long long case2 = curr_dist + price;
                    if (dist[node] > case2){
                        dist[node] = case2;
                        frontier.push({dist[node], node, 0});
                    }

                    long long case3 = curr_dist;
                    if (dist2[node].count(color) == 0 || dist2[node][color] > case3){
                        dist2[node][color] = case3;
                        frontier.push({dist2[node][color], node, color});
                    }
                }
            }
        }
    }

    cout << (dist[n - 1] >= INF ? -1 : dist[n - 1]);
    return 0;
}

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