Submission #1254654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254654		tvgk	Robot (JOI21_ho_t4)	C++20	34 / 100	102 ms	26820 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define task "Robot"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7;
const ll inf = 1e18 + 7;

int n, m, num, c[mxN * 2];
ll mn[mxN * 5], sum[mxN * 5], cost[mxN * 2];
vector<ii> w[mxN];
map<int, int> mp[mxN];

int nen(int j, int c)
{
    if (j > n)
        return j;

    if (!mp[j][c])
        mp[j][c] = ++num;
    return mp[j][c];
}

void Dij(int j)
{
    for (int i = 1; i <= num; i++)
        mn[i] = inf;

    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push({0, j});
    mn[j] = 0;
    while (pq.size())
    {
        ii j = pq.top();
        pq.pop();

        if (j.fi != mn[j.se])
            continue;

        for (ii i : w[j.se])
        {
            if (mn[i.fi] > j.fi + sum[nen(j.se, c[i.se])] - cost[i.se])
            {
                mn[i.fi] = j.fi + sum[nen(j.se, c[i.se])] - cost[i.se];
                pq.push({mn[i.fi], i.fi});
            }

            if (j.se > n)
                continue;

            if (mn[i.fi] > j.fi + cost[i.se])
            {
                mn[i.fi] = j.fi + cost[i.se];
                pq.push({mn[i.fi], i.fi});
            }

            if (mn[nen(i.fi, c[i.se])] > j.fi)
            {
                mn[nen(i.fi, c[i.se])] = j.fi;
                pq.push({j.fi, nen(i.fi, c[i.se])});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    num = n;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v >> c[i] >> cost[i];

        w[u].push_back({v, i});
        w[v].push_back({u, i});

        sum[nen(u, c[i])] += cost[i];
        w[nen(u, c[i])].push_back({v, i});

        sum[nen(v, c[i])] += cost[i];
        w[nen(v, c[i])].push_back({u, i});
    }

    Dij(1);
    if (mn[n] == inf)
        cout << -1;
    else
        cout << mn[n];
}

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