# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
516434 |
2022-01-21T10:04:24 Z |
XII |
Robot (JOI21_ho_t4) |
C++17 |
|
1150 ms |
102344 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "QG04PAINT"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int N = 1e5 + 1;
const ll INF = 1e18;
int n, m;
using pi = pair<int, int>;
map<int, vector<pi>> adj[N];
map<int, bool> vis[N];
map<int, ll> sum[N];
map<int, ll> d[N];
using node = pair<ll, pair<int, int>>;
priority_queue<node, vector<node>, greater<node>> pq;
ll dijkstra(const int &s, const int &e){
d[e][0] = INF;
pq.emplace(0, mp(s, 0));
d[s][0] = 0;
while(!pq.empty()){
ll wu = pq.top().fi;
auto [u, cu] = pq.top().se;
pq.pop();
if(wu != d[u][cu] || vis[u][cu]) continue;
vis[u][cu] = true;
// cout << u << " " << c << " " << wu << "?\n";
if(cu){
for(auto [v, wv]: adj[u][cu]){
ll tmp = wu + (sum[u][cu] - wv);
if(!d[v].count(0) || d[v][0] > tmp){
d[v][0] = tmp;
pq.emplace(tmp, mp(v, 0));
}
}
} else{
for(auto [cv, ed]: adj[u]){
for(auto [v, wv]: ed){
ll tmp = wu + min(1LL * wv, sum[u][cv] - wv);
if(!d[v].count(0) || d[v][0] > tmp){
d[v][0] = tmp;
pq.emplace(tmp, mp(v, 0));
}
if(!d[v].count(cv) || d[v][cv] > wu){
d[v][cv] = wu;
pq.emplace(d[v][cv], mp(v, cv));
}
}
}
}
}
return d[e][0] == INF ? -1 : d[e][0];
}
int main(){
IOS;
Fi();
cin >> n >> m;
FORU(i, 1, m){
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u][c].eb(v, p);
adj[v][c].eb(u, p);
sum[u][c] += p;
sum[v][c] += p;
}
cout << dijkstra(1, n);
return 0;
}
Compilation message
Main.cpp: In function 'void Fi()':
Main.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen(PROB".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen(PROB".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
19020 KB |
Output is correct |
2 |
Correct |
9 ms |
19056 KB |
Output is correct |
3 |
Correct |
9 ms |
19112 KB |
Output is correct |
4 |
Correct |
9 ms |
19020 KB |
Output is correct |
5 |
Correct |
9 ms |
19148 KB |
Output is correct |
6 |
Correct |
8 ms |
18988 KB |
Output is correct |
7 |
Correct |
10 ms |
19260 KB |
Output is correct |
8 |
Correct |
9 ms |
19148 KB |
Output is correct |
9 |
Correct |
13 ms |
19916 KB |
Output is correct |
10 |
Correct |
18 ms |
19788 KB |
Output is correct |
11 |
Correct |
14 ms |
19460 KB |
Output is correct |
12 |
Correct |
14 ms |
19532 KB |
Output is correct |
13 |
Correct |
12 ms |
19556 KB |
Output is correct |
14 |
Correct |
14 ms |
19532 KB |
Output is correct |
15 |
Correct |
10 ms |
19404 KB |
Output is correct |
16 |
Correct |
11 ms |
19532 KB |
Output is correct |
17 |
Correct |
11 ms |
19560 KB |
Output is correct |
18 |
Correct |
10 ms |
19276 KB |
Output is correct |
19 |
Correct |
10 ms |
19276 KB |
Output is correct |
20 |
Correct |
11 ms |
19404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
41836 KB |
Output is correct |
2 |
Correct |
92 ms |
31372 KB |
Output is correct |
3 |
Correct |
192 ms |
33928 KB |
Output is correct |
4 |
Correct |
151 ms |
35016 KB |
Output is correct |
5 |
Correct |
1046 ms |
101996 KB |
Output is correct |
6 |
Correct |
809 ms |
88140 KB |
Output is correct |
7 |
Correct |
333 ms |
62948 KB |
Output is correct |
8 |
Correct |
390 ms |
62032 KB |
Output is correct |
9 |
Correct |
418 ms |
62144 KB |
Output is correct |
10 |
Correct |
353 ms |
56840 KB |
Output is correct |
11 |
Correct |
126 ms |
33280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
19020 KB |
Output is correct |
2 |
Correct |
9 ms |
19056 KB |
Output is correct |
3 |
Correct |
9 ms |
19112 KB |
Output is correct |
4 |
Correct |
9 ms |
19020 KB |
Output is correct |
5 |
Correct |
9 ms |
19148 KB |
Output is correct |
6 |
Correct |
8 ms |
18988 KB |
Output is correct |
7 |
Correct |
10 ms |
19260 KB |
Output is correct |
8 |
Correct |
9 ms |
19148 KB |
Output is correct |
9 |
Correct |
13 ms |
19916 KB |
Output is correct |
10 |
Correct |
18 ms |
19788 KB |
Output is correct |
11 |
Correct |
14 ms |
19460 KB |
Output is correct |
12 |
Correct |
14 ms |
19532 KB |
Output is correct |
13 |
Correct |
12 ms |
19556 KB |
Output is correct |
14 |
Correct |
14 ms |
19532 KB |
Output is correct |
15 |
Correct |
10 ms |
19404 KB |
Output is correct |
16 |
Correct |
11 ms |
19532 KB |
Output is correct |
17 |
Correct |
11 ms |
19560 KB |
Output is correct |
18 |
Correct |
10 ms |
19276 KB |
Output is correct |
19 |
Correct |
10 ms |
19276 KB |
Output is correct |
20 |
Correct |
11 ms |
19404 KB |
Output is correct |
21 |
Correct |
231 ms |
41836 KB |
Output is correct |
22 |
Correct |
92 ms |
31372 KB |
Output is correct |
23 |
Correct |
192 ms |
33928 KB |
Output is correct |
24 |
Correct |
151 ms |
35016 KB |
Output is correct |
25 |
Correct |
1046 ms |
101996 KB |
Output is correct |
26 |
Correct |
809 ms |
88140 KB |
Output is correct |
27 |
Correct |
333 ms |
62948 KB |
Output is correct |
28 |
Correct |
390 ms |
62032 KB |
Output is correct |
29 |
Correct |
418 ms |
62144 KB |
Output is correct |
30 |
Correct |
353 ms |
56840 KB |
Output is correct |
31 |
Correct |
126 ms |
33280 KB |
Output is correct |
32 |
Correct |
115 ms |
25792 KB |
Output is correct |
33 |
Correct |
167 ms |
31096 KB |
Output is correct |
34 |
Correct |
539 ms |
57996 KB |
Output is correct |
35 |
Correct |
386 ms |
48676 KB |
Output is correct |
36 |
Correct |
341 ms |
59668 KB |
Output is correct |
37 |
Correct |
402 ms |
60844 KB |
Output is correct |
38 |
Correct |
417 ms |
64632 KB |
Output is correct |
39 |
Correct |
132 ms |
28092 KB |
Output is correct |
40 |
Correct |
438 ms |
62076 KB |
Output is correct |
41 |
Correct |
439 ms |
62068 KB |
Output is correct |
42 |
Correct |
569 ms |
70168 KB |
Output is correct |
43 |
Correct |
217 ms |
40884 KB |
Output is correct |
44 |
Correct |
427 ms |
41924 KB |
Output is correct |
45 |
Correct |
390 ms |
60152 KB |
Output is correct |
46 |
Correct |
324 ms |
60524 KB |
Output is correct |
47 |
Correct |
362 ms |
60892 KB |
Output is correct |
48 |
Correct |
1150 ms |
102344 KB |
Output is correct |