# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
388202 |
2021-04-10T13:37:38 Z |
BartolM |
Robot (JOI21_ho_t4) |
C++17 |
|
2564 ms |
130168 KB |
#define DEBUG 1
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
const int INF=0x3f3f3f3f;
const int N=8e5+5;
const ll MAX=(ll)INF*INF;
int n, m, uk;
map <pii, int> boja, koji;
map <pii, ll> zbr;
ll dist[N];
vector <pil> ls[N];
set <pli> S;
void dijkstra() {
fill(dist, dist+N, MAX);
dist[1]=0;
S.insert(mp(0, 1));
while (!S.empty()) {
pli node=*S.begin();
S.erase(S.begin());
for (pil sus:ls[node.Y]) {
if (dist[sus.X]<=sus.Y+node.X) continue;
if (S.count(mp(dist[sus.X], sus.X))) S.erase(mp(dist[sus.X], sus.X));
dist[sus.X]=node.X+sus.Y;
S.insert(mp(dist[sus.X], sus.X));
}
}
}
void solve() {
uk=n+1;
for (int i=1; i<=n; ++i) {
for (int j=0; j<ls[i].size(); ++j) {
pil sus=ls[i][j];
if (sus.X>n) continue;
int boj=boja[{i, sus.X}];
if (!koji[{i, boj}]) {
ls[i].pb(mp(uk, 0));
koji[{i, boj}]=uk++;
}
int node=koji[{i, boj}];
ls[sus.X].pb(mp(node, 0));
ls[node].pb(mp(sus.X, zbr[{i, boj}]-sus.Y));
assert( zbr[mp(i, boj)]>=sus.Y );
}
}
dijkstra();
printf("%lld\n", dist[n]>=MAX ? -1 : dist[n]);
}
void load() {
scanf("%d %d", &n, &m);
for (int i=0; i<m; ++i) {
int a, b, boj, cos;
scanf("%d %d %d %d", &a, &b, &boj, &cos);
ls[a].pb(mp(b, cos)); ls[b].pb(mp(a, cos));
boja[{a, b}]=boj;
boja[{b, a}]=boj;
if (zbr.count({a, boj})) zbr[{a, boj}]+=cos;
else zbr[{a, boj}]=cos;
if (zbr.count({b, boj})) zbr[{b, boj}]+=cos;
else zbr[{b, boj}]=cos;
}
}
int main() {
load();
solve();
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int j=0; j<ls[i].size(); ++j) {
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void load()':
Main.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
69 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
72 | scanf("%d %d %d %d", &a, &b, &boj, &cos);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
25292 KB |
Output is correct |
2 |
Correct |
16 ms |
25292 KB |
Output is correct |
3 |
Correct |
16 ms |
25312 KB |
Output is correct |
4 |
Correct |
17 ms |
25240 KB |
Output is correct |
5 |
Correct |
16 ms |
25292 KB |
Output is correct |
6 |
Correct |
16 ms |
25292 KB |
Output is correct |
7 |
Correct |
19 ms |
25548 KB |
Output is correct |
8 |
Correct |
18 ms |
25420 KB |
Output is correct |
9 |
Correct |
23 ms |
26380 KB |
Output is correct |
10 |
Correct |
27 ms |
26300 KB |
Output is correct |
11 |
Correct |
21 ms |
26112 KB |
Output is correct |
12 |
Correct |
24 ms |
25976 KB |
Output is correct |
13 |
Correct |
23 ms |
26184 KB |
Output is correct |
14 |
Correct |
22 ms |
26124 KB |
Output is correct |
15 |
Correct |
22 ms |
25756 KB |
Output is correct |
16 |
Correct |
23 ms |
26064 KB |
Output is correct |
17 |
Correct |
25 ms |
25972 KB |
Output is correct |
18 |
Correct |
21 ms |
25628 KB |
Output is correct |
19 |
Correct |
24 ms |
26036 KB |
Output is correct |
20 |
Correct |
20 ms |
25832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
576 ms |
58968 KB |
Output is correct |
2 |
Correct |
238 ms |
41460 KB |
Output is correct |
3 |
Correct |
757 ms |
68236 KB |
Output is correct |
4 |
Correct |
329 ms |
47284 KB |
Output is correct |
5 |
Correct |
2517 ms |
127272 KB |
Output is correct |
6 |
Correct |
2125 ms |
115208 KB |
Output is correct |
7 |
Correct |
1524 ms |
106432 KB |
Output is correct |
8 |
Correct |
1717 ms |
95364 KB |
Output is correct |
9 |
Correct |
1630 ms |
95352 KB |
Output is correct |
10 |
Correct |
1000 ms |
80148 KB |
Output is correct |
11 |
Correct |
635 ms |
63240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
25292 KB |
Output is correct |
2 |
Correct |
16 ms |
25292 KB |
Output is correct |
3 |
Correct |
16 ms |
25312 KB |
Output is correct |
4 |
Correct |
17 ms |
25240 KB |
Output is correct |
5 |
Correct |
16 ms |
25292 KB |
Output is correct |
6 |
Correct |
16 ms |
25292 KB |
Output is correct |
7 |
Correct |
19 ms |
25548 KB |
Output is correct |
8 |
Correct |
18 ms |
25420 KB |
Output is correct |
9 |
Correct |
23 ms |
26380 KB |
Output is correct |
10 |
Correct |
27 ms |
26300 KB |
Output is correct |
11 |
Correct |
21 ms |
26112 KB |
Output is correct |
12 |
Correct |
24 ms |
25976 KB |
Output is correct |
13 |
Correct |
23 ms |
26184 KB |
Output is correct |
14 |
Correct |
22 ms |
26124 KB |
Output is correct |
15 |
Correct |
22 ms |
25756 KB |
Output is correct |
16 |
Correct |
23 ms |
26064 KB |
Output is correct |
17 |
Correct |
25 ms |
25972 KB |
Output is correct |
18 |
Correct |
21 ms |
25628 KB |
Output is correct |
19 |
Correct |
24 ms |
26036 KB |
Output is correct |
20 |
Correct |
20 ms |
25832 KB |
Output is correct |
21 |
Correct |
576 ms |
58968 KB |
Output is correct |
22 |
Correct |
238 ms |
41460 KB |
Output is correct |
23 |
Correct |
757 ms |
68236 KB |
Output is correct |
24 |
Correct |
329 ms |
47284 KB |
Output is correct |
25 |
Correct |
2517 ms |
127272 KB |
Output is correct |
26 |
Correct |
2125 ms |
115208 KB |
Output is correct |
27 |
Correct |
1524 ms |
106432 KB |
Output is correct |
28 |
Correct |
1717 ms |
95364 KB |
Output is correct |
29 |
Correct |
1630 ms |
95352 KB |
Output is correct |
30 |
Correct |
1000 ms |
80148 KB |
Output is correct |
31 |
Correct |
635 ms |
63240 KB |
Output is correct |
32 |
Correct |
732 ms |
67932 KB |
Output is correct |
33 |
Correct |
713 ms |
62736 KB |
Output is correct |
34 |
Correct |
1241 ms |
85032 KB |
Output is correct |
35 |
Correct |
972 ms |
72096 KB |
Output is correct |
36 |
Correct |
1123 ms |
83868 KB |
Output is correct |
37 |
Correct |
1285 ms |
95784 KB |
Output is correct |
38 |
Correct |
1637 ms |
109996 KB |
Output is correct |
39 |
Correct |
955 ms |
80744 KB |
Output is correct |
40 |
Correct |
1684 ms |
100752 KB |
Output is correct |
41 |
Correct |
1657 ms |
100908 KB |
Output is correct |
42 |
Correct |
1750 ms |
102696 KB |
Output is correct |
43 |
Correct |
671 ms |
65612 KB |
Output is correct |
44 |
Correct |
1418 ms |
93132 KB |
Output is correct |
45 |
Correct |
1220 ms |
85664 KB |
Output is correct |
46 |
Correct |
1076 ms |
79964 KB |
Output is correct |
47 |
Correct |
1231 ms |
91948 KB |
Output is correct |
48 |
Correct |
2564 ms |
130168 KB |
Output is correct |