Submission #534503

#	Time	Username	Problem	Language	Result	Execution time	Memory
534503		someone	Robot (JOI21_ho_t4)	C++14	0 / 100	3054 ms	30628 KiB

Main

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

struct Arc {
    int nex, cost, nb, col;
};

struct Sit {
    bool ch;
    int iArc, 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];

int Dijkstra() {
    for(int i = 0; i < N; i++)
        dist[i] = INF;
    priority_queue<Sit> pq;
    for(int i : adj[0])
        if(arc[i].nb > 1) {
            dist[i] = arc[i].cost;
            pq.push({true, i, arc[i].cost});
        } else {
            dist[i] = 0;
            pq.push({false, i, 0});
        }
    while(!pq.empty()) {
        Sit sit = pq.top();
        if(dist[sit.iArc] == sit.dist) {
            pq.pop();
            int act = arc[sit.iArc].nex;
            if(act == n-1)
                return dist[sit.iArc];
            for(int j : adj[act]) {
                int d = dist[sit.iArc], need = 1;
                if(arc[j].col == arc[sit.iArc].col && sit.ch)
                    need = 2;
                if(arc[j].nb > need)
                    d += arc[j].cost;
                if(d < dist[j]) {
                    dist[j] = d;
                    pq.push({arc[j].nb > need, j, d});
                }
            }
        }
    }
    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]++;
        adj[a].push_back(2*i);
        adj[b].push_back(2*i+1);
        arc.push_back({b, cost, 0, col});
        arc.push_back({a, cost, 0, col});
    }
    
    for(int i = 0; i < 2*m; i++)
        arc[i].nb = occ[arc[i ^1].nex][arc[i].col];
    
    cout << Dijkstra();
}

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