Submission #633690

#	Time	Username	Problem	Language	Result	Execution time	Memory
633690		Blossomstream	Robot (JOI21_ho_t4)	C++17	100 / 100	419 ms	20396 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int c[200000];
int p[200000];
vector<pair<int, pair<int, int> > > adj[100000];
vector<ll> d;
bool visited[100000];
void dijkstra() {
    d.assign(n, LONG_LONG_MAX);
    priority_queue<pair<ll, int> > q;
    d[0] = 0;
    q.push(make_pair(0, 0));
    while(!q.empty()) {
        int v = q.top().second;
        q.pop();
        if(visited[v]) continue;
        visited[v] = true;
        set<int> s;
        for(auto u : adj[v]) {
            s.insert(u.second.first);
        }
        vector<int> v1;
        vector<ll> v2;
        vector<ll> v3;
        while(!s.empty()) {
            v1.push_back(*s.begin());
            s.erase(*s.begin());
            v2.push_back(0);
            v3.push_back(2000000000000000);
        }
        for(auto u : adj[v]) {
            int l = lower_bound(v1.begin(), v1.end(), u.second.first) - v1.begin();
            v2[l] += (ll) u.second.second;
            v3[l] = min(v3[l], d[u.first]);
        }
        for(auto u : adj[v]) {
            if(visited[u.first]) continue;
            int l = lower_bound(v1.begin(), v1.end(), u.second.first) - v1.begin();
            d[u.first] = min(d[u.first], d[v] + ((ll) u.second.second));
            d[u.first] = min(d[u.first], v3[l] + v2[l] - ((ll) u.second.second));
            d[u.first] = min(d[u.first], d[v] + v2[l] - ((ll) u.second.second));
            q.push(make_pair(-d[u.first], u.first));
        }
    }
}
int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b, color, cost;
        cin >> a >> b >> color >> cost;
        a--; b--;
        adj[a].push_back(make_pair(b, make_pair(color, cost)));
        adj[b].push_back(make_pair(a, make_pair(color, cost)));
    }
    dijkstra();
    if(d[n-1] != LONG_LONG_MAX) cout << d[n-1] << endl;
    else cout << -1 << endl;
}

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