oj.uz

Submission #415663

# Submission time Handle Problem Language Result Execution time Memory
415663 2021-06-01T10:45:38 Z ruadhan Robot (JOI21_ho_t4) C++17
0 / 100
 184 ms 17420 KB 
#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];
set<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]);
    }

    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);
            if (dist[v] + w < dist[e.u])
            {
                dist[e.u] = dist[v] + w;
                pq.push({dist[e.u], e.u});
            }
        }
    }

    cout << dist[N] << '\n';

    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 17420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -