Submission #1109550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109550		nh0902	Robot (JOI21_ho_t4)	C++14	100 / 100	718 ms	86772 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 110000;

long long const inf = 1e18;

int n, m;

struct Edge {
    int a, c;
    long long p;
};
map<int, vector<Edge>> v[N];

map<int, long long> ma[N];

long long dp[N];

map<int, long long> D[N];

struct Node {
    int x;
    long long d;
    int c;
};

struct cmp{
    bool operator() (Node u, Node v) {
        return u.d > v.d;
    }
};

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

    cin >> n >> m;

    int a, b, c;
    long long p;

    for (int i = 1; i <= m; i ++) {
        cin >> a >> b >> c >> p;
        v[a][c].push_back({b, c, p});
        v[b][c].push_back({a, c, p});
        ma[a][c] += p;
        ma[b][c] += p;
    }

    priority_queue<Node, vector<Node>, cmp> pq;

    for (int i = 1; i <= n; i ++) {
        dp[i] = inf;
    }

    dp[1] = 0;

    pq.push({1, 0, 0});

    while (!pq.empty()) {
        Node t = pq.top();
        pq.pop();

        if (t.c > 0) {
            if (t.d > D[t.x][t.c]) continue;

            for (Edge e : v[t.x][t.c]) {
                if (e.c == t.c) {
                    long long next_d = t.d + ma[t.x][t.c] - e.p;
                    if (dp[e.a] > next_d) {
                        dp[e.a] = next_d;
                        pq.push({e.a, dp[e.a], 0});
                    }
                }
            }

        }

        else {
            if (t.d > dp[t.x]) continue;
            
            for (auto &i : v[t.x]) {
                for (Edge e : i.second) {
                    if (!D[e.a].count(e.c) || D[e.a][e.c] > t.d) {
                        D[e.a][e.c] = t.d;
                        pq.push({e.a, t.d, e.c});
                    }

                    long long next_d = ma[t.x][e.c] - e.p + t.d;
                    if (dp[e.a] > next_d) {
                        dp[e.a] = next_d;
                        pq.push({e.a, next_d, 0});
                    }

                    next_d = t.d + e.p;
                    if (dp[e.a] > next_d) {
                        dp[e.a] = next_d;
                        pq.push({e.a, next_d, 0});
                    }
                }
                
            }



        }





    }


    if (dp[n] > inf / 2) {
        cout << -1;
        return 0;
    }
    cout << dp[n];

    return 0;
}

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