Submission #526656

#	Time	Username	Problem	Language	Result	Execution time	Memory
526656		Lobo	Robot (JOI21_ho_t4)	C++17	100 / 100	1040 ms	120112 KiB

Main

#include<bits/stdc++.h>
using namespace std;
vector<pair<long long,pair<long long,long long>>> g[220000];
map<long long,vector<pair<long long,long long>>> gc[220000];
map<long long,long long> d[220000], sm[220000];
int32_t main() {
    long long n, m; cin >> n >> m;
    for(long long i = 1; i <= m; i++) {
        long long u, v, c, w; cin >> u >> v >> c >> w;
        g[u].push_back(make_pair(v,make_pair(c,w)));
        g[v].push_back(make_pair(u,make_pair(c,w)));
    }
    for(long long i = 1; i <= n; i++) {
        d[i][0] = 1000000000000000010;
        for(auto V : g[i]) {
            d[i][V.second.first] = 1000000000000000010;
            gc[i][V.second.first].push_back(make_pair(V.first,V.second.second));
            sm[i][V.second.first]+= V.second.second;
        }
    }
    priority_queue<pair<long long,pair<long long,long long>>> pq;
    pq.push(make_pair(0,make_pair(1,0))); d[1][0] = 0;
    while(pq.size()) {
        long long u = pq.top().second.first;
        long long dist = -pq.top().first;
        long long cl = pq.top().second.second;
        pq.pop();
        if(dist != d[u][cl]) continue;
        if(cl == 0) {
            for(auto V : g[u]) {
                long long v = V.first;
                long long c = V.second.first;
                long long w = V.second.second;
                if(d[v][c] > d[u][0]) {
                    d[v][c] = d[u][0];
                    pq.push(make_pair(-d[v][c],make_pair(v,c)));
                }
                if(d[v][0] > d[u][0] + min(sm[u][c]-w,w)) {
                    d[v][0] = d[u][0] + min(sm[u][c]-w,w);
                    pq.push(make_pair(-d[v][0],make_pair(v,0)));
                }
            }
        }
        else {
            for(auto V : gc[u][cl]) {
                long long v = V.first;
                long long w = V.second;
                long long c = cl;
                if(d[v][0] > d[u][c] + sm[u][c] - w) {
                    d[v][0] = d[u][c] + sm[u][c] - w;
                    pq.push(make_pair(-d[v][0],make_pair(v,0)));
                }
            }
        }
    }
    if(d[n][0] == 1000000000000000010) cout << -1 << endl;
    else cout << d[n][0] << endl;
}

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