Submission #784574

#	Time	Username	Problem	Language	Result	Execution time	Memory
784574		borisAngelov	Robot (JOI21_ho_t4)	C++17	34 / 100	3109 ms	1292680 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const long long inf = 1e18;

int n, m;

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

map<int, vector<edge>> g[maxn];

long long dist[maxn];

map<int, long long> dp[maxn];
map<int, long long> sum[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, p;
        cin >> x >> y >> col >> p;

        g[x][col].push_back({y, col, p});
        g[y][col].push_back({x, col, p});

        sum[x][col] += p;
        sum[y][col] += p;
    }

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

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

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

        pq.pop();

        if (col != 0 && dp[node][col] == curr)
        {
            for (auto e : g[node][col])
            {
                long long path = curr + sum[node][col] - e.price;

                if (dist[e.to] > path)
                {
                    dist[e.to] = path;
                    pq.push(make_pair(-path, make_pair(e.to, 0)));
                }
            }
        }
        else if (col == 0 && dist[node] == curr)
        {
            for (int i = 0; i < g[node].size(); ++i)
            {
                vector<edge> edges = g[node][i];

                for (int j = 0; j < edges.size(); ++j)
                {
                    edge e = edges[j];

                    long long path1 = curr + sum[node][e.col] - e.price;

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

                    long long path2 = curr + e.price;

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

                    long long path3 = curr;

                    if (dp[e.to].find(e.col) == dp[e.to].end() || path3 < dp[e.to][e.col])
                    {
                        dp[e.to][e.col] = path3;
                        pq.push(make_pair(-path3, make_pair(e.to, e.col)));
                    }
                }
            }
        }
    }

    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:81:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for (int i = 0; i < g[node].size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~
Main.cpp:85:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 for (int j = 0; j < edges.size(); ++j)
      |                                 ~~^~~~~~~~~~~~~~

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