Submission #424390

#	Time	Username	Problem	Language	Result	Execution time	Memory
424390		Harry464	Robot (JOI21_ho_t4)	C++14	100 / 100	1741 ms	116804 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <set>
#include <map>

using namespace std;
typedef long long ll;


map<ll, vector <pair<ll, ll> > > adjl[100005];

map <ll, ll> boje[100005];
map <ll, ll> put[100005];

vector <set <ll> > post(100005);

vector <vector <pair <ll, pair<ll, ll> > > > dadjl(100005);

int main()
{

    ll n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++){

        ll u, v, c, p;
        cin >> u >> v >> c >> p;
        u--, v--;

        boje[u][c] += p;
        boje[v][c] += p;
        adjl[u][c].push_back(make_pair(v, p)), adjl[v][c].push_back(make_pair(u, p));
        dadjl[u].push_back(make_pair(v, make_pair(c,p))), dadjl[v].push_back(make_pair(u, make_pair(c,p)));

    }

    vector <ll> mini(n + 1, 1000000000000000000);
    mini[0] = 0;

    priority_queue <pair <ll, pair<ll,pair<ll,ll> > > > dijk;
    dijk.push(make_pair(0, make_pair(0, make_pair(-1,0))));

    while (dijk.size()){

        ll pric = -dijk.top().first, u = dijk.top().second.first, ori = dijk.top().second.second.first, col = dijk.top().second.second.second;

        //if (pric == 0)
            //cout << u << endl;

        dijk.pop();

        if (dadjl[u].size() == 0)
            continue;

        if (col > 0){

            if (put[u][col] != pric)
                continue;

            for (pair <ll,ll> i : adjl[u][col]){

                ll v = i.first, pri = i.second;

                ll prelaz = boje[u][col] - pri + pric;

                if (prelaz  < mini[v])
                    mini[v] = prelaz, dijk.push(make_pair(-prelaz, make_pair(v, make_pair(u, 0))));

            }

        } else {

           if (mini[u] != pric)
             continue;

           for (auto pp : dadjl[u]){

                ll  v = pp.first, c = pp.second.first, pri = pp.second.second;

                ll prelaz = min(pric + boje[u][c] - pri, pric + pri);

                // << prelaz << endl;

                if (prelaz < mini[v])
                   mini[v] = prelaz, dijk.push(make_pair(-prelaz, make_pair(v, make_pair(u, 0))));


                if (!post[v].count(c) || pric < put[v][c])
                    post[v].insert(c), put[v][c] = pric, dijk.push(make_pair(-pric, make_pair(v, make_pair(u, c))));


           }


        }


    }

    if (mini[n-1] == 1000000000000000000)
        cout << "-1";
    else
        cout << mini[n-1];

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:50:67: warning: unused variable 'ori' [-Wunused-variable]
   50 |         ll pric = -dijk.top().first, u = dijk.top().second.first, ori = dijk.top().second.second.first, col = dijk.top().second.second.second;
      |                                                                   ^~~

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