Submission #688960

#	Time	Username	Problem	Language	Result	Execution time	Memory
688960		JooDdae	Robot (JOI21_ho_t4)	C++17	0 / 100	329 ms	49168 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;

int n, m;
map<int, vector<array<int, 2>>> v1[100100], v2[100100];
map<int, ll> s[100100];
map<int, array<ll, 2>> d[100100];
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int x, y, c, p; cin >> x >> y >> c >> p;
        s[x][c] += p, s[y][c] += p, d[x][c] = d[y][c] = {INF, INF};
        v1[x][c].push_back({y, p}), v1[y][c].push_back({x, p});
        v2[x][c].push_back({y, p}), v2[y][c].push_back({x, p});
    }

    pq.push({0, 1, -1, 0});
    while(!pq.empty()) {
        auto [c, u, col, type] = pq.top(); pq.pop();
        if(d[u][col][type] < c) continue;
        if(u == n) return cout << c, 0;

        auto it = v1[u].begin();
        while(it != v1[u].end()) {
            if(type && it->first == col) { it++; continue; }

            auto &[xcol, v] = *it;

            ll p = s[u][xcol];
            for(auto [x, y] : v) {
                ll C1 = c + y, C2 = c + p - y;
                if(C1 < d[x][xcol][1]) d[x][xcol][1] = C1, pq.push({C1, x, xcol, 1});
                if(C2 < d[x][xcol][0]) d[x][xcol][0] = C2, pq.push({C2, x, xcol, 0});
            }

            it = v1[u].erase(it);
        }

        if(type == 1) continue;

        // 변경된 색으로 들어와서 변경되기 전 색과 같은 간선의 색을 다시 변경해서 나가는 처리

        auto &v = v2[u][col];
        ll p = s[u][col];
        if(v.size() > 1) for(auto [x, y] : v) {
            ll C = c+p-y-1;
            if(C < d[x][col][0]) d[x][col][0] = C, pq.push({C, x, col, 0});
        }
        v2[u].erase(col);
    }

    cout << -1;
}

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