Submission #1092142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092142		jonghak9028	Robot (JOI21_ho_t4)	C++17	34 / 100	3024 ms	104424 KiB

Main

/* ************************************************************************** */
/*                                                                            */
/*                                                      :::    :::    :::     */
/*   Problem Number: 20987                             :+:    :+:      :+:    */
/*                                                    +:+    +:+        +:+   */
/*   By: js9028 <boj.kr/u/js9028>                    +#+    +#+          +#+  */
/*                                                  +#+      +#+        +#+   */
/*   https://boj.kr/20987                          #+#        #+#      #+#    */
/*   Solved: 2024/09/23 13:56:09 by js9028        ###          ###   ##.kr    */
/*                                                                            */
/* ************************************************************************** */
#include <bits/stdc++.h>
using namespace std;
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
typedef long long ll;
typedef long double lld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int MAXSIZE = 2000000;
const long long INF = 1e18 + 5;
const double EPSILON = 1e-14;
const ll DIV = 2000003;
const long double pi = 3.14159265358979323846264338327950288419716939937510L;

int n, m;
map<pair<int, int>, ll> clv; // (node, color) = sum
vector<array<int, 3>> adj[100055];
map<pair<int, int>, ll> color; // node, node  color
map<pair<int, int>, ll> cost;  //(node, node) cost
map<array<int, 3>, ll> dist;   // (cur node, prv node, use) = dist

ll solve()
{
    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll,4>>> pq;

    pq.push({0, 1, 1, 1});
    dist[{1, 0, 1}] = 0;
    while (!pq.empty())
    {
        auto p = pq.top();
        int cur = p[1], prv = p[2];
        ll dis = p[0];
        int u = p[3];
        pq.pop();
        if (cur == n)
            return dis;
        if (dist[{cur, prv, u}] < dis)
            continue;

        for (auto &nxt : adj[cur])
        {
            ll nd = dis + nxt[2];
            if (dist.find({nxt[0], cur, 0}) == dist.end() || dist[{nxt[0], cur, 0}] > nd)
            {
                dist[{nxt[0], cur, 0}] = nd;
                pq.push({nd, nxt[0], cur, 0});
            }
            if (u == 0)
            {
                nd = dis + clv[{cur, nxt[1]}] - nxt[2] - (nxt[1] == color[{cur, prv}] ? cost[{cur, prv}] : 0ll);
            }
            else
            {
                nd = dis + clv[{cur, nxt[1]}] - nxt[2];
            }

            if (dist.find({nxt[0], cur, 1}) == dist.end() || dist[{nxt[0], cur, 1}] > nd)
            {
                dist[{nxt[0], cur, 1}] = nd;
                pq.push({nd, nxt[0], cur, 1});
            }
        }
    }
    return -1;
}

int main()
{
    fastio;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        adj[a].push_back({b, c, p});
        adj[b].push_back({a, c, p});
        clv[{a, c}] += p;
        clv[{b, c}] += p;
        cost[{a, b}] = p;
        cost[{b, a}] = p;
        color[{a, b}] = c;
        color[{b, a}] = c;
    }

    cout << solve();
    return 0;
}

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