Submission #784144

#	Time	Username	Problem	Language	Result	Execution time	Memory
784144		borisAngelov	Robot (JOI21_ho_t4)	C++17	0 / 100	1268 ms	21872 KiB

Main

#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 (stderr)

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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42