Submission #494875

#	Time	Username	Problem	Language	Result	Execution time	Memory
494875		leu_naut	Robot (JOI21_ho_t4)	C++11	100 / 100	971 ms	87452 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define FOR(i,a,b) for (int i = a; i <= b; ++i)
#define f first
#define s second
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0);
#define ii pair <int,int>
#define pii pair <ll,ll>
#define all(x) x.begin(),x.end()

const int N = 1e5;
const ll oo = 1e18;

struct Edge
{
    int v; ll p;
    int tp;
};

map <int, vector <Edge>> g[N + 5];
map <int,ll> dp2[N + 5], psum[N + 5];
ll dp[N + 5];

int main()
{
    FastIO
    int n,m;
    cin >> n >> m;
    FOR(i,1,m)
    {
        int a,b,c,p;
        cin >> a >> b >> c >> p;
        g[a][c].push_back({b,p,c});
        g[b][c].push_back({a,p,c});
        psum[a][c] += p;
        psum[b][c] += p;
    }

    FOR(i,1,n) dp[i] = oo;
    dp[1] = 0;
    priority_queue <tuple <ll, int , int>> q;
    q.push({0,1,0});

    while (!q.empty()) {
        ll cost, node, c;
        tie(cost, node, c) = q.top();
        q.pop();
        if (c) {
            for (Edge j : g[node][c]) {
                ll case1 = psum[node][c] - j.p - cost;
                if (case1 < dp[j.v]) {
                    dp[j.v] = case1;
                    q.push({-dp[j.v], j.v, 0});
                }
            }
        }
        else {
            if (dp[node] != -cost) continue;
            for (auto i : g[node]) {
                for (Edge j : i.s) {
                    // Don't pick j, change j's neighbour.
                    ll case1 = psum[node][j.tp] - j.p - cost;
                    if (case1 < dp[j.v]) {
                        dp[j.v] = case1;
                        q.push({-dp[j.v], j.v, 0});
                    }

                    // Pick j & not change its neighbor.
                    ll case2 = j.p - cost;
                    if (case2 < dp[j.v]) {
                        dp[j.v] = case2;
                        q.push({-dp[j.v], j.v, 0});
                    }

                    // Pick j & change its neighbor.

                    ll case3 = -cost;
                    if (!dp2[j.v][j.tp] || case3 < dp2[j.v][j.tp]) {
                        dp2[j.v][j.tp] = case3;
                        q.push({-dp2[j.v][j.tp], j.v, j.tp});
                    }
                }
            }
        }
    }
    if (dp[n] != oo) cout << dp[n];
    else cout << -1;
}

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