Submission #1092269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092269		jonghak9028	Robot (JOI21_ho_t4)	C++17	100 / 100	879 ms	30648 KiB

Main

/* ************************************************************************** */
/*                                                                            */
/*                                                      :::    :::    :::     */
/*   Problem Number: 20987                             :+:    :+:      :+:    */
/*                                                    +:+    +:+        +:+   */
/*   By: js9028 <boj.kr/u/js9028>                    +#+    +#+          +#+  */
/*                                                  +#+      +#+        +#+   */
/*   https://boj.kr/20987                          #+#        #+#      #+#    */
/*   Solved: 2024/09/23 23:22:22 by js9028        ###          ###   ##.kr    */
/*                                                                            */
/* ************************************************************************** */
#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
#include <string>
#include <array>
#include <math.h>
#include <tuple>
#include <map>
#include <queue>
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
using namespace std;

typedef long long ll;
const long long INF = 1e15 + 5;

int n, m;
vector<array<int, 3>> adj[100011];
ll dist[3][100011];

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

    fill(dist[0], dist[0] + n + 3, INF);
    fill(dist[1], dist[1] + n + 3, INF);
    dist[0][1] = dist[1][1] = 0;
    pq.push({0, 1, 0});
    pq.push({0, 1, 1});
    while (!pq.empty())
    {
        auto [dis, cur, y] = pq.top();
        pq.pop();
        if (cur == n)
            return dis;
        if (dist[y][cur] < dis)
            continue;
        map<int, ll> mn, sum, sz;
        for (auto [nxt, clr, cos] : adj[cur])
        {
            if (mn.find(clr) == mn.end())
                mn[clr] = min(dist[1][nxt], dist[0][nxt]);

            else
                mn[clr] = min(mn[clr], min(dist[1][nxt], dist[0][nxt]));
            sum[clr] += cos;
            sz[clr]++;
        }
        for (auto [nxt, clr, cos] : adj[cur])
        {
            ll nd = dis + cos;
            if (dist[1][nxt] > nd)
            {
                dist[1][nxt] = nd;
                pq.push({nd, nxt, 1});
            }
            nd = INF;
            if (sz[clr] > 1)
                nd = mn[clr] + sum[clr] - cos;

            nd = min(nd, dis + sum[clr] - cos);

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

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

    cout << solve();
    return 0;
}

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