Submission #587990

#	Time	Username	Problem	Language	Result	Execution time	Memory
587990		Peti	Robot (JOI21_ho_t4)	C++14	24 / 100	1000 ms	108972 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e18;
vector<vector<pair<int, long long>>> g;
vector<map<int, int>> inds; 
int n, m;

inline int get(int x, int c){
    if(inds[x].count(c)) return inds[x][c];
    g[x].emplace_back((int)g.size(), 0);
    g.push_back(vector<pair<int, long long>>());
    inds[x][c] = (int)g.size() - 1;
    return (int)g.size() - 1;
}

vector<long long> dijkstra(){
    priority_queue<pair<long long, int>> pq;
    pq.push({0, 0});
    vector<long long> tav(g.size(), INF);
    vector<bool> volt(g.size(), false);
    tav[0] = 0;
    while(!pq.empty()){
        while(!pq.empty() && volt[pq.top().second]) pq.pop();
        if(pq.empty()) break;
        int x = pq.top().second;
        pq.pop();
        volt[x] = true;
        for(auto e : g[x]){
            if(!volt[e.first] && tav[e.first] > tav[x] + e.second){
                tav[e.first] = tav[x] + e.second;
                pq.push({-tav[e.first], e.first});
            }
        }
    }
    return tav;
}

void add(int x, int y, int c){
    g[x].emplace_back(y, c);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m;

    g.resize(n);
    inds.resize(n);
    vector<map<int, vector<pair<int, int>>>> elek(n);
    for(int i = 0; i < n; i++) inds[i][0] = i;
    for(int i = 0; i < m; i++){
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        --a, --b;
        elek[a][c].emplace_back(b, d);
        elek[b][c].emplace_back(a, d);
    }

    for(int i = 0; i < n; i++){
        for(auto p : elek[i]){
            long long ossz = 0;
            for(auto e : p.second) ossz += e.second;
            for(auto e : p.second){
                add(get(i, p.first), get(e.first, 0), ossz - e.second);
                add(get(i, 0), get(e.first, 0), e.second);
                add(get(i, 0), get(e.first, p.first), 0);
            }
        }
    }

    long long d = dijkstra()[n-1];
    cout<<(d < INF ? d : -1)<<'\n';

    return 0;
}

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