Submission #1109408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109408		nh0902	Robot (JOI21_ho_t4)	C++14	0 / 100	3070 ms	66708 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 110000;

long long const inf = 1e16;

int n, m;

struct Edge {
    int a, c;
    long long p;
};
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;
    long long p;
    int pa;
};

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].push_back({b, c, p});
        v[b].push_back({a, c, p});
    }

    for (int i = 1; i <= n; i ++) {
        for (Edge e : v[i]) {
            if (ma[i].find(e.c) == ma[i].end()) {
                ma[i][e.c] = 0;
            }
            ma[i][e.c] += e.p;
        }
    }

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

    for (int i = 1; i <= n; i ++) {
        for (Edge e : v[i]) {
            D[i][e.c] = inf;
        }
        dp[i] = inf;
    }

    dp[1] = 0;

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

    while (!pq.empty()) {
        Node t = pq.top();
        pq.pop();
        if (t.c > 0 && t.d > D[t.x][t.c]) continue;
        if (t.c == 0 && t.d > dp[t.x]) continue;


        for (Edge e : v[t.x]) {
            if (D[e.a][e.c] > t.d + e.p) {
                D[e.a][e.c] = t.d + e.p;
                pq.push({e.a, t.d + e.p, e.c, e.p, t.x});
            }

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

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


            }
        }
    }
    long long ans = dp[n];
    for (auto d : D[n]) {
        ans = min(ans, d.second);
    }
    if (ans == inf) {
        cout << -1;
        return 0;
    }
    cout << ans;

    return 0;
}

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