Submission #424390

# Submission time Handle Problem Language Result Execution time Memory
424390 2021-06-11T21:39:49 Z Harry464 Robot (JOI21_ho_t4) C++14
100 / 100
1741 ms 116804 KB
#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

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;
      |                                                                   ^~~
# Verdict Execution time Memory Grader output
1 Correct 16 ms 21324 KB Output is correct
2 Correct 14 ms 21324 KB Output is correct
3 Correct 15 ms 21384 KB Output is correct
4 Correct 16 ms 21332 KB Output is correct
5 Correct 14 ms 21448 KB Output is correct
6 Correct 16 ms 21448 KB Output is correct
7 Correct 19 ms 21580 KB Output is correct
8 Correct 15 ms 21452 KB Output is correct
9 Correct 20 ms 22224 KB Output is correct
10 Correct 20 ms 22176 KB Output is correct
11 Correct 18 ms 21964 KB Output is correct
12 Correct 18 ms 21836 KB Output is correct
13 Correct 18 ms 21964 KB Output is correct
14 Correct 18 ms 21968 KB Output is correct
15 Correct 17 ms 21784 KB Output is correct
16 Correct 20 ms 21964 KB Output is correct
17 Correct 21 ms 21968 KB Output is correct
18 Correct 16 ms 21584 KB Output is correct
19 Correct 20 ms 21896 KB Output is correct
20 Correct 17 ms 21836 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 354 ms 49172 KB Output is correct
2 Correct 193 ms 35292 KB Output is correct
3 Correct 428 ms 47268 KB Output is correct
4 Correct 223 ms 39864 KB Output is correct
5 Correct 1691 ms 110840 KB Output is correct
6 Correct 1550 ms 101584 KB Output is correct
7 Correct 609 ms 76676 KB Output is correct
8 Correct 828 ms 75268 KB Output is correct
9 Correct 828 ms 75412 KB Output is correct
10 Correct 584 ms 68160 KB Output is correct
11 Correct 276 ms 46104 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 16 ms 21324 KB Output is correct
2 Correct 14 ms 21324 KB Output is correct
3 Correct 15 ms 21384 KB Output is correct
4 Correct 16 ms 21332 KB Output is correct
5 Correct 14 ms 21448 KB Output is correct
6 Correct 16 ms 21448 KB Output is correct
7 Correct 19 ms 21580 KB Output is correct
8 Correct 15 ms 21452 KB Output is correct
9 Correct 20 ms 22224 KB Output is correct
10 Correct 20 ms 22176 KB Output is correct
11 Correct 18 ms 21964 KB Output is correct
12 Correct 18 ms 21836 KB Output is correct
13 Correct 18 ms 21964 KB Output is correct
14 Correct 18 ms 21968 KB Output is correct
15 Correct 17 ms 21784 KB Output is correct
16 Correct 20 ms 21964 KB Output is correct
17 Correct 21 ms 21968 KB Output is correct
18 Correct 16 ms 21584 KB Output is correct
19 Correct 20 ms 21896 KB Output is correct
20 Correct 17 ms 21836 KB Output is correct
21 Correct 354 ms 49172 KB Output is correct
22 Correct 193 ms 35292 KB Output is correct
23 Correct 428 ms 47268 KB Output is correct
24 Correct 223 ms 39864 KB Output is correct
25 Correct 1691 ms 110840 KB Output is correct
26 Correct 1550 ms 101584 KB Output is correct
27 Correct 609 ms 76676 KB Output is correct
28 Correct 828 ms 75268 KB Output is correct
29 Correct 828 ms 75412 KB Output is correct
30 Correct 584 ms 68160 KB Output is correct
31 Correct 276 ms 46104 KB Output is correct
32 Correct 367 ms 46012 KB Output is correct
33 Correct 384 ms 46488 KB Output is correct
34 Correct 780 ms 73204 KB Output is correct
35 Correct 598 ms 60972 KB Output is correct
36 Correct 563 ms 66128 KB Output is correct
37 Correct 672 ms 71120 KB Output is correct
38 Correct 729 ms 84388 KB Output is correct
39 Correct 389 ms 53644 KB Output is correct
40 Correct 892 ms 76528 KB Output is correct
41 Correct 889 ms 76872 KB Output is correct
42 Correct 898 ms 87084 KB Output is correct
43 Correct 400 ms 53116 KB Output is correct
44 Correct 834 ms 67120 KB Output is correct
45 Correct 705 ms 69364 KB Output is correct
46 Correct 558 ms 68276 KB Output is correct
47 Correct 590 ms 69632 KB Output is correct
48 Correct 1741 ms 116804 KB Output is correct