Submission #393872

#	Time	Username	Problem	Language	Result	Execution time	Memory
393872		nohaxjustsoflo	Robot (JOI21_ho_t4)	C++17	0 / 100	664 ms	57844 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, c;
    ll p;
};

vector<edge> adj[mxN];
map<int, ll> costs[mxN]; ///at each node its edge's color sum

ll best[mxN][2]; /// node, parent changed
bool done[mxN][2]; /// node, parent changed

struct pos
{
    int i;
    int pchange;
    int pcolor;
    ll pcost;
    int prev;
    bool operator<(const pos& p) const
    {
        return pcost < p.pcost;
    }
};

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, c; ll p; cin >> u >> v >> c >> p;
        adj[u].push_back({v, c, p});
        costs[u][c] += p;
        adj[v].push_back({u, c, p});
        costs[v][c] += p;
    }
    for(int i = 0; i < mxN; i++)
    {
        best[i][0] = best[i][1] = 1e18;
    }
    best[1][0] = 0;
    priority_queue<pair<ll, pos>> q;
    q.push({0, {1, 0, 0, 0, 0}});
    ll ans = -1;
    while(!q.empty())
    {
        auto cur = q.top(); q.pop();
        ll cost = -cur.first;
        int i = cur.second.i;
        bool p = cur.second.pchange;
        int pcolor = cur.second.pcolor;
        ll pcost = cur.second.pcost;
        int prev = cur.second.prev;
        //if(done[i][p]) continue;
        //done[i][p]=1;
        if(i == n)
        {
            ans = cost;
            break;
        }
        if(p)
        {
            for(edge e : adj[i])
            {
                int j = e.j;
                ll c = e.p;
                int color = e.c;
                if(cost + c < best[j][1]) ///promeni sebe
                {
                    best[j][1] = cost + c;
                    q.push({-best[j][1], {j, 1, color, c, i}});
                }
                //if pcolor == e.color
                if(pcolor == color && prev != j)
                {
                    if(costs[i][color] - c - pcost + cost < best[j][0]) ///promeni sve ostale
                    {
                        best[j][0] = costs[i][color] - c - pcost + cost;
                        q.push({-best[j][0], {j, 0, 0, 0}});
                    }
                }
                else
                {
                    if(costs[i][color] - c + cost < best[j][0]) ///promeni sve ostale
                    {
                        best[j][0] = costs[i][color] - c + cost;
                        q.push({-best[j][0], {j, 0, 0, 0}});
                    }
                }
            }
        }
        else
        {
            for(edge e : adj[i])
            {
                int j = e.j;
                ll c = e.p;
                int color = e.c;
                if(cost + c < best[j][1]) ///promeni sebe
                {
                    best[j][1] = cost + c;
                    q.push({-best[j][1], {j, 1, color, c, i}});
                }
                if(costs[i][color] - c + cost < best[j][0]) ///promeni sve ostale
                {
                    best[j][0] = costs[i][color] - c + cost;
                    q.push({-best[j][0], {j, 0, 0, 0}});
                }
            }
        }
    }
    cout << ans;
}
/*
6 4
GGPPG
*/

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