Submission #621158

#	Time	Username	Problem	Language	Result	Execution time	Memory
621158		leroycut	Robot (JOI21_ho_t4)	C++17	100 / 100	1072 ms	85728 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const ll N = 203, mod = 1e9 + 7, inf = 1e18 + 7;

struct node
{
    int to, col;
    ll cost;
};

struct uz
{   
    ll cost;
    int to, col;
    friend bool operator<(const uz& a, const uz& b){
        if(a.cost == b.cost){
            if(a.to == b.to){
                return a.col < b.col;
            }
            return a.to < b.to;
        }
        return a.cost < b.cost;
    }
};



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

    // freopen("fortmoo.in", "r", stdin);
    // freopen("fortmoo.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<map<int, vector<node>>> g(n);
    vector<map<int, ll>> sum(n), dp2(n);
    vector<ll> dp(n, inf);

    for(int i = 0; i < m; ++i){
        int a, b, c;
        ll p;
        cin >> a >> b >> c >> p;
        --a, --b;
        g[a][c].push_back({b, c, p});
        g[b][c].push_back({a, c, p});
        sum[a][c] += p;
        sum[b][c] += p;
    }

    set<uz> s;
    s.insert({0, 0, 0});
    dp[0] = 0;

    while(!s.empty()){
        auto v = *s.begin();
        s.erase(s.begin());
        // cout << v.to << "\n";

        if(v.col){
            for(auto j : g[v.to][v.col]){
                ll cost = v.cost + sum[v.to][v.col] - j.cost;
                if(cost < dp[j.to]){
                    s.erase({dp[j.to], j.to, 0});
                    dp[j.to] = cost;
                    s.insert({cost, j.to, 0});
                }
            }
        }else{
            for(auto i : g[v.to]){
                for(auto j : i.second){
                    ll cost1;
                    cost1 = v.cost + j.cost;
                    if(cost1 < dp[j.to]){
                        s.erase({dp[j.to], j.to, 0});
                        dp[j.to] = cost1;
                        s.insert({cost1, j.to, 0});
                    }

                    ll cost2;
                    cost2 = v.cost + sum[v.to][j.col] - j.cost;
                    if(cost2 < dp[j.to]){
                        s.erase({dp[j.to], j.to, 0});
                        dp[j.to] = cost2;
                        s.insert({cost2, j.to, 0});
                    }

                    ll cost3 = v.cost;
                    if(!dp2[j.to].count(j.col)){
                        s.erase({dp2[j.to][j.col], j.to, j.col});
                        dp2[j.to][j.col] = cost3;
                        s.insert({cost3, j.to, j.col});
                    }
                    else if(cost3 < dp2[j.to][j.col]){
                        s.erase({dp2[j.to][j.col], j.to, j.col});
                        dp2[j.to][j.col] = cost3;
                        s.insert({cost3, j.to, j.col});
                    }
                }
            }
        }
    }
    if(dp[n - 1] == inf){
        cout << -1;
    }else{
        cout << dp[n - 1];
    }
}

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