Submission #1286093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286093		nemkho	Robot (JOI21_ho_t4)	C++20	0 / 100	3098 ms	77404 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pr pair <ll, int>
#define fi first
#define se second
using namespace std;
const ll inf = 1e18;
const int N = 1e5 + 5;
map <int, ll> sum[N], dc[N];
map <int, vector<pr>> a[N];
int n, m;
ll res, d[N];
struct haha
{
    ll dist;
    int to, color;
};
struct cmp
{
    bool operator() (const haha &a, const haha &b)
    {
        return a.dist > b.dist;
    }
};
void inp()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        ll w;
        cin >> x >> y >> c >> w;
        a[x][c].push_back({w, y});
        a[y][c].push_back({w, x});
        sum[x][c] += w;
        sum[y][c] += w;
      //  cout << sum[4][3] << "\n";
    }
}
void dijkstra()
{
    priority_queue <haha, vector<haha>, cmp> q;
    q.push({0, 1, 0});
    for (int i = 1; i <= n; i++)
        d[i] = inf;
    d[1] = 0;
    while (!q.empty())
    {
        int u = q.top().to, color = q.top().color;
        ll k = q.top().dist;
        q.pop();
       // cout << u << " " << color << " " << k << "\n";
        if (!color && k < d[u])
            continue;
        if (color && k > dc[u][color])
            continue;
        for (auto &i : a[u])
        {
            for (auto &j : i.se)
            {
                int v = j.se;
                ll w = j.fi;
                if (i.fi == color)
                {
                    if (d[v] > k + w)
                    {
                        d[v] = k + w;
                        q.push({d[v], v, 0});
                    }
                }
                else
                {
                    if (d[v] > k + w)
                    {
                        d[v] = k + w;
                        q.push({d[v], v, 0});
                    }
                    if (!dc[v].count(i.fi) || dc[v][i.fi] > k + sum[u][i.fi] - w)
                    {
                        dc[v][i.fi] = k + sum[u][i.fi] - w;
                      //  cout << sum[u][i.fi] - w << " " << u << " " << v << " " << i.fi << "\n";
                        q.push({dc[v][i.fi], v, i.fi});
                    }
                }
            }
        }
    }
}
void solve()
{
    dijkstra();
    res = d[n];
    for (auto i : dc[n])
        res = min(res, i.se);
    cout << (res == inf ? -1 : res);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    inp();
    solve();
}

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