Submission #393908

#	Time	Username	Problem	Language	Result	Execution time	Memory
393908		nohaxjustsoflo	Robot (JOI21_ho_t4)	C++17	100 / 100	1097 ms	100128 KiB

Main

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
const int mxN = 2e5+5;
const int mod = 1e9+7;

struct edge
{
    int j, color;
    ll cost;
};

map<int, vector<edge>> adj[mxN];
map<int, ll> costs[mxN];

ll dp1[mxN]; ///best to come node i
map<int, ll> dp2[mxN]; ///best to come to node i with color c

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

    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int u, v, color; ll cost; cin >> u >> v >> color >> cost;
        adj[u][color].push_back({v, color, cost});
        costs[u][color] += cost;
        adj[v][color].push_back({u, color, cost});
        costs[v][color] += cost;
    }
    for(int i = 0; i < mxN; i++)
    {
        dp1[i] = 1e18;
    }
    dp1[1] = 0;
    priority_queue<pair<ll, pair<int, int>>> q;
    q.push({0, {1, 0}});
    ll ans = 1e18;
    while(!q.empty())
    {
        auto cur = q.top(); q.pop();
        int color = cur.second.second;
        int i = cur.second.first;
        ll cost = -cur.first;
        if(i == n && color == 0)
        {
            ans = cost; break;
        }
        if(color)
        {
            if(cost > dp2[i][color]) continue;
            ///idi na sve boje color za swap sve sem te 1
            for(edge e : adj[i][color])
            {
                if(cost + costs[i][color] - e.cost < dp1[e.j]) ///1
                {
                    dp1[e.j] = cost + costs[i][e.color] - e.cost;
                    q.push({-dp1[e.j], {e.j,0}});
                }
            }
        }
        else
        {
            if(cost > dp1[i]) continue;
            ///promeni sve ostale nastavi bez colora 1
            ///promeni sebe instant 2
            ///promeni sebe al na ler 3
            for(auto mp : adj[i])
            {
                for(edge e : mp.second)
                {
                    if(cost + e.cost < dp1[e.j]) /// 2
                    {
                        dp1[e.j] = cost + e.cost;
                        q.push({-dp1[e.j], {e.j, 0}});
                    }
                    if(cost + costs[i][e.color] - e.cost < dp1[e.j]) ///1
                    {
                        dp1[e.j] = cost + costs[i][e.color] - e.cost;
                        q.push({-dp1[e.j], {e.j,0}});
                    }
                    if(dp2[e.j].find(e.color)==dp2[e.j].end() || cost < dp2[e.j][e.color])
                    {
                        dp2[e.j][e.color] = cost;
                        q.push({-cost, {e.j, e.color}});
                    }
                }
            }
        }
    }
    if(ans > 1e17) cout << "-1";
    else cout << ans;
}
/*
6 4
GGPPG
*/

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