oj.uz

Submission #784144

# Submission time Handle Problem Language Result Execution time Memory
784144 2023-07-15T18:44:13 Z borisAngelov Robot (JOI21_ho_t4) C++17
0 / 100
 1268 ms 21872 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const long long inf = (1LL << 62);

int n, m;

struct edge
{
    int to;
    int col;
    int price;
};

vector<edge> graph[maxn];

vector<pair<int, int>> g[maxn];

long long dist[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, col, price;
        cin >> x >> y >> col >> price;

        graph[x].push_back({y, col, price});
        graph[y].push_back({x, col, price});
    }

    for (int i = 1; i <= n; ++i)
    {
        vector<int> cnt(m + 5, 0);

        for (int j = 0; j < graph[i].size(); ++j)
        {
            ++cnt[graph[i][j].col];
        }

        for (int j = 0; j < graph[i].size(); ++j)
        {
            int c = graph[i][j].col;
            int to = graph[i][j].to;

            if (cnt[c] == 1)
            {
                g[i].push_back(make_pair(to, 0));
            }
            else
            {
                g[i].push_back(make_pair(to, graph[i][j].price));
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
    }

    priority_queue<pair<long long, int>> pq;
    pq.push(make_pair(0LL, 1));

    dist[1] = 0LL;

    while (!pq.empty())
    {
        int node = pq.top().second;
        long long curr = -pq.top().first;

        pq.pop();

        for (int i = 0; i < g[node].size(); ++i)
        {
            int to = g[node][i].first;
            long long path = curr + g[node][i].second;

            if (dist[to] > path)
            {
                dist[to] = path;
                pq.push(make_pair(-path, to));
            }
        }
    }

    if (dist[n] == inf)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << dist[n] << endl;
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j = 0; j < graph[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~
Main.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int j = 0; j < graph[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~
Main.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 12120 KB Output is correct
2 Correct 41 ms 8184 KB Output is correct
3 Correct 171 ms 16336 KB Output is correct
4 Correct 86 ms 10004 KB Output is correct
5 Incorrect 1268 ms 21872 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

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