제출 #1109570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1109570		nh0902	Robot (JOI21_ho_t4)	C++14	0 / 100	3066 ms	65648 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;
};
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});
        ma[a][c] += p;
        ma[b][c] += p;
    }

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

    for (int i = 2; 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 (e.c == t.c) {
                long long next_d = (t.d - t.p) + 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});
                }


            }

            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 (dp[e.a] > t.d + e.p) {
                dp[e.a] = t.d + e.p;
                pq.push({e.a, t.d + e.p, e.c, e.p, t.x});
            }

            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 / 2) {
        cout << -1;
        return 0;
    }
    cout << ans;

    return 0;
}

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