Submission #534536

#	Time	Username	Problem	Language	Result	Execution time	Memory
534536		someone	Robot (JOI21_ho_t4)	C++14	24 / 100	856 ms	87468 KiB

Main

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

struct Arc {
    int nex, cost, cost2, nb, col, skip = -1;
};

struct Sit {
    int i, dist;
    
    bool operator <(const Sit& other) const {
        return dist > other.dist;
    }
};

const int N = 2e5 + 42, INF = 1e18;

vector<Arc> arc;
int n, m, dist[N];
vector<int> adj[N];
map<int, int> occ[N], prix[N];

int Dijkstra() {
    for(int i = 1; i < N; i++)
        dist[i] = INF;
    priority_queue<Sit> pq;
    pq.push({0, 0});
    while(!pq.empty()) {
        Sit sit = pq.top();
        pq.pop();
        int i = sit.i, d = sit.dist;
        if(d == dist[i]) {
            for(int j : adj[i]) {
                int dist2 = d;
                if(arc[j].nb > 1)
                    dist2 += arc[j].cost;
                if(dist2 < dist[arc[j].nex]) {
                    dist[arc[j].nex] = dist2;
                    pq.push({arc[j].nex, dist2});
                }
                if(arc[j].skip != -1) {
                    dist2 = d + arc[j].cost2;
                    if(dist2 < dist[arc[j].skip]) {
                        dist[arc[j].skip] = dist2;
                        pq.push({arc[j].skip, dist2});
                    }
                }
            }
        }
    }
    if(dist[n-1] != INF)
        return dist[n-1];
    return -1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b, col, cost;
        cin >> a >> b >> col >> cost;
        a--, b--;
        occ[a][col]++;
        occ[b][col]++;
        prix[a][col] += cost;
        prix[b][col] += cost;
        adj[a].push_back(2*i);
        adj[b].push_back(2*i+1);
        arc.push_back({b, cost, cost, 0, col});
        arc.push_back({a, cost, cost, 0, col});
    }
    
    for(int i = 0; i < n; i++)
        for(int j : adj[i])
            arc[j].nb = occ[i][arc[j].col],
            arc[j].cost = min(arc[j].cost, prix[i][arc[j].col] - arc[j].cost);
    
    for(int i = 0; i < n; i++) {
        map<int, int> first;
        for(int j : adj[i]) {
            if(first.find(arc[j].col) == first.end())
                first[arc[j].col] = j;
            else if(arc[j].nb == 2) {
                arc[j ^ 1].skip = arc[first[arc[j].col]].nex;
                arc[first[arc[j].col] ^ 1].skip = arc[j].nex;
            }
        }
    }
    
    cout << Dijkstra();
}

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