제출 #1183995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183995		jerzyk	Robot (JOI21_ho_t4)	C++20	100 / 100	295 ms	53756 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 100 * 1000 + 7;
bool vis[N];
vector<pair<int, pair<ll, int>>> ed[N];
vector<ll> odl[N], sum[N];
vector<int>st[N];
map<int, int> col[N];

void Dijkstra()
{
    int v, r; priority_queue<pair<ll, pair<int, int>>> q;
    odl[1][0] = 0;
    q.push(make_pair(0, make_pair(1, 0)));
    while(q.size() > 0)
    {
        v = q.top().nd.st; r = q.top().nd.nd;
        q.pop();
        if(r > 0)
        {
            int co = col[v][r];
            ll s = sum[v][co];
            for(int i = st[v][co]; ed[v][i].st == r && i < (int)ed[v].size(); ++i)
            {
                ll o = odl[v][co] + s - ed[v][i].nd.st;
                if(!vis[ed[v][i].nd.nd] && odl[ed[v][i].nd.nd][0] > o)
                {
                    odl[ed[v][i].nd.nd][0] = o;
                    q.push(make_pair(-o, make_pair(ed[v][i].nd.nd, 0)));
                }
            }
            continue;
        }
        if(vis[v]) continue;
        vis[v] = true;
        int curc = 0;
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(i == 0 || ed[v][i].st != ed[v][i - 1].st) ++curc;
            int ne = ed[v][i].nd.nd;
            ll o = odl[v][0]; int co = col[ne][ed[v][i].st];
            if(odl[ne][co] > o)
            {
                odl[ne][co] = o;
                q.push(make_pair(-o, make_pair(ne, ed[v][i].st)));
            }
            o += ed[v][i].nd.st;
            o = min(o, odl[v][0] + sum[v][curc] - ed[v][i].nd.st);
            if(odl[ne][0] > o)
            {
                odl[ne][0] = o;
                q.push(make_pair(-o, make_pair(ne, 0)));
            }
        }
    }
}

void Solve()
{
    int n, m, a, b, d, c;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> a >> b >> c >> d;
        ed[a].pb(make_pair(c, make_pair(d, b)));
        ed[b].pb(make_pair(c, make_pair(d, a)));
    }
    for(int i = 1; i <= n; ++i)
    {
        sort(ed[i].begin(), ed[i].end());
        odl[i].pb(I); sum[i].pb(I); st[i].pb(-1);
        for(int j = 0; j < (int)ed[i].size(); ++j)
        {
            if(j == 0 || ed[i][j].st != ed[i][j - 1].st)
            {
                odl[i].pb(I); sum[i].pb(0LL); st[i].pb(j);
                col[i][ed[i][j].st] = st[i].size() - 1;
            }
            sum[i][sum[i].size() - 1] += ed[i][j].nd.st;
        }
    }
    Dijkstra();
    if(odl[n][0] == I)
        cout << -1 << "\n";
    else
        cout << odl[n][0] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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