oj.uz

Submission #415670

# Submission time Handle Problem Language Result Execution time Memory
415670 2021-06-01T10:56:51 Z ruadhan Robot (JOI21_ho_t4) C++17
0 / 100
 182 ms 33820 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];
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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 5 ms 7356 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7348 KB Output is correct
5 Correct 5 ms 7348 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Incorrect 6 ms 7488 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 16744 KB Output is correct
2 Correct 71 ms 12380 KB Output is correct
3 Runtime error 174 ms 33820 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 5 ms 7356 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7348 KB Output is correct
5 Correct 5 ms 7348 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Incorrect 6 ms 7488 KB Output isn't correct
8 Halted 0 ms 0 KB -