Submission #1222523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222523		badge881	Robot (JOI21_ho_t4)	C++20	24 / 100	86 ms	19544 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct kraw
{
    int a;
    int v;
    int c;
    ll p;
};

const int MAXN = 100 * 1000 + 1;
const int MAXM = 200 * 1000 + 1;
bool odw[MAXN];
vector<kraw> graf[MAXN];
priority_queue<pair<int, int>> pq;
ll odl[MAXN];
ll summ[MAXM];
ll minn[MAXM];

int main()
{

    int n, m, a, b;
    scanf("%d %d", &n, &m);

    kraw x;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d %lld", &x.a, &x.v, &x.c, &x.p);
        graf[x.a].push_back(x);
        swap(x.a, x.v);
        graf[x.a].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        odl[i] = LLONG_MAX / ll(1000);

    pq.push({0, 1});
    odl[1] = 0;

    while (!pq.empty())
    {
        ll aktodl = -pq.top().first;
        int v = pq.top().second;

        pq.pop();

        if (odw[v])
            continue;
        
        odw[v] = true;

        for (auto x : graf[v])
        {
            summ[x.c] = 0LL;
            minn[x.c] = LLONG_MAX / ll(1000);
        }

        for (auto x : graf[v])
            summ[x.c] += x.p;

        for (auto x : graf[v])
            minn[x.c] = min(minn[x.c], odl[x.v] + summ[x.c]);

        for (auto u : graf[v])
        {
            ll x = min({odl[v] + u.p, odl[v] + summ[u.c] - u.p, minn[u.c] - u.p});
            if (x < odl[u.v])
            {
                odl[u.v] = x;
                pq.push({-x, u.v});
            }
        }
    }

    if (odl[n] >= LLONG_MAX / ll(1000))
    {
        printf("-1\n");
        return 0;
    }

    printf("%lld\n", odl[n]);

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d %d %d %lld", &x.a, &x.v, &x.c, &x.p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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