Submission #990546

#	Time	Username	Problem	Language	Result	Execution time	Memory
990546		KietJ	Robot (JOI21_ho_t4)	C++17	100 / 100	773 ms	85956 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair <int, int> ii;
typedef tuple <ll, int, int> DT;

const int N = 2e5 + 1;
const int mod = 998244353;

map <int, ll> dp2[N];
map<int, vector <ii>> ed[N];

void solve() {
    int n, m; cin >> n >> m;
    map <ii, ll> sve;
    for(int i = 0; i < m; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        ed[u][c].push_back({v, d});
        ed[v][c].push_back({u, d});
        sve[{u, c}] += d;
        sve[{v, c}] += d;
    }

    vector <ll> dp1(n + 1, 1e18); 
    priority_queue <DT, vector <DT>, greater <DT>> pq;

    pq.push({0, 1, 0});
    dp1[1] = 0; 

    while (sz(pq)) {
        ll w; 
        int u, c;
        tie(w, u, c) = pq.top();
        pq.pop();

        if (c) {
            if (dp2[u][c] != w) continue;

            for(auto x: ed[u][c]) {
                int v = x.f;
                ll _d = sve[{u, c}] - x.s;
                if (dp1[v] > w + _d) {
                    dp1[v] = w + _d;
                    pq.push({dp1[v], v, 0});
                }
            }
        } else {
            if (dp1[u] != w) continue;
            for(map <int, vector<ii>>::iterator it = ed[u].begin(); it != ed[u].end(); it++) {
                for(auto x: it -> second) {
                    int v = x.f, _c = it -> f;
                    ll _d = x.s;

                    if (dp1[v] > w + min(_d, sve[{u, _c}] - _d)) {
                        dp1[v] = w + min(_d, sve[{u, _c}] - _d);
                        pq.push({dp1[v], v, 0});
                    }

                    if ((dp2[v].count(_c) && dp2[v][_c] > w) || !dp2[v].count(_c)) {
                        dp2[v][_c] = w;
                        pq.push({w, v, _c});
                    }
                }
            }
        }
    }

    cout << (dp1[n] != 1e18 ? dp1[n] : -1) << "\n";
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    // freopen("ROBOT.INP", "r", stdin);
    // freopen("ROBOT.OUT", "w", stdout);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

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