Submission #830642

#	Time	Username	Problem	Language	Result	Execution time	Memory
830642		RaresFelix	Robot (JOI21_ho_t4)	C++17	24 / 100	3055 ms	1069972 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int MN = 100001;
int n, m;
struct Edge {
    int cul, cost, dest;
};
vector<Edge> L[MN];
vector<pair<int, ll> > G[MN]; /// nod, cost
ll Cost[MN];
map<int, int> Fr[MN], Suma[MN];
map<int, pair<int, int> > Other[MN];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int u, v, c, w; 
        cin >> u >> v >> c >> w;
        L[u].push_back({c, w, v});
        L[v].push_back({c, w, u});
    }
    for(int i = 1; i <= n; ++i) {
        for(auto it : L[i]) {
            ++Fr[i][it.cul];
            Suma[i][it.cul] += it.cost;
        }
        for(auto &it : L[i]) {
            it.cost = min(it.cost, Suma[i][it.cul] - it.cost);
        }
        for(auto it : L[i]) {
            if(Fr[i][it.cul] == 1) {
                G[i].push_back(make_pair(it.dest, 0));
            }
            else {
                if(Fr[i][it.cul] == 2) {
                    if(!Other[i].count(it.cul)) Other[i][it.cul] = make_pair(it.dest, it.cost);
                    else {
                        int a = Other[i][it.cul].first, b = it.dest, cul = it.cul;
                        ll ca = Other[i][it.cul].second, cb = it.cost, c = min(ca, cb);
                        if(Fr[a][cul] == 1)
                            G[a].push_back(make_pair(b, c));
                        else 
                            G[a].push_back(make_pair(b, ca));

                        if(Fr[b][cul] == 1)
                            G[b].push_back(make_pair(a, c));
                        else
                            G[b].push_back(make_pair(a, cb));
                    }
                }
                G[i].push_back(make_pair(it.dest, it.cost));
            }
        }
    }
    priority_queue<pair<ll, int> > PQ;
    PQ.push(make_pair(0ll, 1));
    for(int i = 1; i <= n; ++i) Cost[i] = INF;
    Cost[1] = 0;
    while(!PQ.empty()) {
        ll nod = PQ.top().second, cost = - PQ.top().first;
        PQ.pop();
        if(Cost[nod] != cost) continue;
        for(auto [it, w] : G[nod]) {
            if(Cost[it] > Cost[nod] + w) {
                Cost[it] = Cost[nod] + w;
                PQ.push(make_pair(-Cost[it], it));
            }
        }
    }
    if(Cost[n] == INF) {
        cout << "-1\n";
    }  else {
        cout << Cost[n] << "\n";
    }
    return 0;
}

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