Submission #1109559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109559		nh0902	Robot (JOI21_ho_t4)	C++14	0 / 100	3071 ms	66856 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});
    }
 
    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) {
                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});
                }
              
 
            }
            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 / 2) {
        cout << -1;
        return 0;
    }
    cout << ans;
 
    return 0;
}

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