제출 #1255863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255863		papaulo	Robot (JOI21_ho_t4)	C++20	100 / 100	837 ms	83820 KiB

Main

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

using ll = long long;
#define MAXN 100100
map<int, pair<ll, vector<pair<int, int>>>> adj[MAXN];
int vis[MAXN];
map<int, vector<int>> visc[MAXN];

void add(int v, int u, int c, int p) {
    auto pt=adj[v].find(c);
    if(pt==adj[v].end()) {
        adj[v][c]={0LL, vector<pair<int, int>>()};
        pt=adj[v].find(c);
    }
    pt->second.first+=p;
    pt->second.second.push_back({u, p});
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    while(m--) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        add(a, b, c, p);
        add(b, a, c, p);
    }

    priority_queue<pair<pair<ll, int>, pair<int, int>>> pq;
    pq.push({{0, 1}, {0, 0}});
    while(!pq.empty()) {
        auto pr=pq.top();
        pq.pop();
        ll d = -pr.first.first;
        int v=pr.first.second;
        int c=pr.second.first;
        int src=pr.second.second;
        if(!c) {
            if(v==n) {
                cout << d << endl;
                return 0;
            }
            if(vis[v]) continue;
            vis[v]=1;
            for(auto pr : adj[v]) {
                pq.push({{-d, v}, {pr.first, 0}});
            }
            for(auto pr1 : adj[v]) {
                auto &vec=pr1.second.second;
                for(auto pr2 : vec) {
                    pq.push({{-d, pr2.first}, {pr1.first, v}});
                    pq.push({{-(d+pr2.second), pr2.first}, {0, 0}});
                }
            }
        } else {
            auto p = visc[v].find(c);
            if(p==visc[v].end()) {
                visc[v][c]={};
                p=visc[v].find(c);
            }
            auto &vec=p->second;
            if(vec.size()<2) {
                vec.push_back(src);
                auto p2=adj[v].find(c);
                auto &vec=p2->second.second;
                for(auto pr: vec) {
                    if(pr.first==src) continue;
                    ll newd=d+p2->second.first-pr.second;
                    pq.push({{-newd, pr.first}, {0, 0}});
                }
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

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