제출 #1286109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286109		nemkho	Robot (JOI21_ho_t4)	C++20	0 / 100	99 ms	33068 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;
        if (color == 0)
        {
            for (auto &i : a[u])
            {
                for (auto &j : i.se)
                {
                    int v = j.se;
                    ll w = j.fi;
                    if (d[v] > k + w)
                    {
                        d[v] = k + w;
                        q.push({d[v], v, 0});
                    }
                    ll val = d[u] + sum[u][i.fi] - w;
                    if (d[v] > d[u] + sum[u][i.fi] - w)
                    {
                        q.push({val, v, 0});
                        d[v] = val;
                    }
                    if (!dc[v].count(i.fi) || dc[v][i.fi] > k)
                    {
                            dc[v][i.fi] = k;
                          //  cout << sum[u][i.fi] - w << " " << u << " " << v << " " << i.fi << "\n";
                            q.push({k, v, i.fi});
                    }
                }
            }
        }
        else
        {
            for (pr i : a[u][color])
            {
                int v = i.se;
                ll w = i.fi;
                ll val = k + sum[u][color] - w;
                if (d[v] > val)
                {
                    d[v] = val;
                    q.push({val, v, 0});
                }
            }
        }
    }
}
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