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