제출 #415670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415670		ruadhan	Robot (JOI21_ho_t4)	C++17	0 / 100	182 ms	33820 KiB

Main

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

const int MX = 1e5 + 5;

struct Edge
{
    int u;
    int color;
    ll price;
};

// vector<pair<int, ll>> adj[MX];
vector<Edge> adj[MX];
int A[MX], B[MX], C[2 * MX];
ll P[2 * MX];
ll dist[MX];
map<int, int> colors[MX];

int N, M;

int main()
{
    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        cin >> A[i] >> B[i] >> C[i] >> P[i];
        adj[A[i]].push_back({B[i], C[i], P[i]});
        adj[B[i]].push_back({A[i], C[i], P[i]});
        // colors[A[i]].insert(C[i]);
        // colors[B[i]].insert(C[i]);
        colors[A[i]][C[i]]++;
        colors[B[i]][C[i]]++;
    }

    using T = pair<ll, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    pq.push({0, 1});

    for (int i = 1; i <= N; i++)
        dist[i] = LONG_LONG_MAX;
    dist[1] = 0;

    while (!pq.empty())
    {
        auto curr = pq.top();
        pq.pop();
        int v = curr.second;
        if (dist[v] < curr.first)
            continue;
        for (auto e : adj[v])
        {
            // ll w = (colors[v].find(e.color) == colors[v].end() ? 0 : e.price);
            ll w = (colors[v][e.color] == 1 ? 0 : e.price);
            if (dist[v] + w < dist[e.u])
            {
                dist[e.u] = dist[v] + w;
                pq.push({dist[e.u], e.u});
            }
        }
    }

    if (dist[N] == LONG_LONG_MAX)
        cout << -1 << '\n';
    else
        cout << dist[N] << '\n';

    return 0;
}

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