# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
858328 |
2023-10-08T06:26:13 Z |
phoenix0423 |
Robot (JOI21_ho_t4) |
C++17 |
|
815 ms |
77108 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int N = 1e9 + 7;
const ll INF = 1e18;
struct edge{
int to, p, c;
edge(){}
edge(int _to, int _p, int _c) : to(_to), p(_p), c(_c){}
};
vector<edge> adj[maxn];
map<int, int> col[maxn];
map<int, ll> dist[maxn], ttl[maxn]; // dist[pos][0] = no change
int main(void){
fastio;
int n, m;
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b, c, p;
cin>>a>>b>>c>>p;
a--, b--;
adj[a].pb(edge(b, p, c));
adj[b].pb(edge(a, p, c));
col[a][c] ++, col[b][c] ++;
ttl[a][c] += p, ttl[b][c] += p;
}
for(int i = 0; i < n; i++){
for(auto [c, cnt] : col[i]) dist[i][c] = INF;
dist[i][0] = INF;
}
dist[0][0] = 0;
priority_queue<pll, vector<pll>, greater<pll>> q;
q.push({0, 0});
while(!q.empty()){
auto [d, pos] = q.top(); q.pop();
if(dist[pos][0] != d) continue;
for(auto [x, p, c] : adj[pos]){
dist[x][c] = min(dist[x][c], dist[pos][0]);
if(dist[x][0] > dist[pos][0] + p) dist[x][0] = dist[pos][0] + p, q.push({dist[x][0], x});
if(dist[x][0] > min(dist[pos][c], dist[pos][0]) + ttl[pos][c] - p) dist[x][0] = min(dist[pos][c], dist[pos][0]) + ttl[pos][c] - p, q.push({dist[x][0], x});
}
}
cout<<(dist[n - 1][0] < INF ? dist[n - 1][0] : -1)<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
4 ms |
16676 KB |
Output is correct |
3 |
Correct |
4 ms |
16984 KB |
Output is correct |
4 |
Correct |
4 ms |
16732 KB |
Output is correct |
5 |
Correct |
4 ms |
16732 KB |
Output is correct |
6 |
Correct |
3 ms |
16732 KB |
Output is correct |
7 |
Correct |
4 ms |
17040 KB |
Output is correct |
8 |
Correct |
4 ms |
16888 KB |
Output is correct |
9 |
Correct |
6 ms |
17244 KB |
Output is correct |
10 |
Correct |
5 ms |
17224 KB |
Output is correct |
11 |
Correct |
4 ms |
17240 KB |
Output is correct |
12 |
Correct |
5 ms |
17240 KB |
Output is correct |
13 |
Correct |
5 ms |
16988 KB |
Output is correct |
14 |
Correct |
5 ms |
16988 KB |
Output is correct |
15 |
Correct |
6 ms |
16936 KB |
Output is correct |
16 |
Correct |
5 ms |
16984 KB |
Output is correct |
17 |
Correct |
5 ms |
17240 KB |
Output is correct |
18 |
Correct |
4 ms |
16936 KB |
Output is correct |
19 |
Correct |
5 ms |
16984 KB |
Output is correct |
20 |
Correct |
5 ms |
17192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
33616 KB |
Output is correct |
2 |
Correct |
37 ms |
25688 KB |
Output is correct |
3 |
Correct |
80 ms |
29136 KB |
Output is correct |
4 |
Correct |
52 ms |
28496 KB |
Output is correct |
5 |
Correct |
815 ms |
74692 KB |
Output is correct |
6 |
Correct |
549 ms |
66036 KB |
Output is correct |
7 |
Correct |
229 ms |
48828 KB |
Output is correct |
8 |
Correct |
242 ms |
48464 KB |
Output is correct |
9 |
Correct |
270 ms |
48372 KB |
Output is correct |
10 |
Correct |
171 ms |
47056 KB |
Output is correct |
11 |
Correct |
91 ms |
38952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
4 ms |
16676 KB |
Output is correct |
3 |
Correct |
4 ms |
16984 KB |
Output is correct |
4 |
Correct |
4 ms |
16732 KB |
Output is correct |
5 |
Correct |
4 ms |
16732 KB |
Output is correct |
6 |
Correct |
3 ms |
16732 KB |
Output is correct |
7 |
Correct |
4 ms |
17040 KB |
Output is correct |
8 |
Correct |
4 ms |
16888 KB |
Output is correct |
9 |
Correct |
6 ms |
17244 KB |
Output is correct |
10 |
Correct |
5 ms |
17224 KB |
Output is correct |
11 |
Correct |
4 ms |
17240 KB |
Output is correct |
12 |
Correct |
5 ms |
17240 KB |
Output is correct |
13 |
Correct |
5 ms |
16988 KB |
Output is correct |
14 |
Correct |
5 ms |
16988 KB |
Output is correct |
15 |
Correct |
6 ms |
16936 KB |
Output is correct |
16 |
Correct |
5 ms |
16984 KB |
Output is correct |
17 |
Correct |
5 ms |
17240 KB |
Output is correct |
18 |
Correct |
4 ms |
16936 KB |
Output is correct |
19 |
Correct |
5 ms |
16984 KB |
Output is correct |
20 |
Correct |
5 ms |
17192 KB |
Output is correct |
21 |
Correct |
102 ms |
33616 KB |
Output is correct |
22 |
Correct |
37 ms |
25688 KB |
Output is correct |
23 |
Correct |
80 ms |
29136 KB |
Output is correct |
24 |
Correct |
52 ms |
28496 KB |
Output is correct |
25 |
Correct |
815 ms |
74692 KB |
Output is correct |
26 |
Correct |
549 ms |
66036 KB |
Output is correct |
27 |
Correct |
229 ms |
48828 KB |
Output is correct |
28 |
Correct |
242 ms |
48464 KB |
Output is correct |
29 |
Correct |
270 ms |
48372 KB |
Output is correct |
30 |
Correct |
171 ms |
47056 KB |
Output is correct |
31 |
Correct |
91 ms |
38952 KB |
Output is correct |
32 |
Correct |
79 ms |
23660 KB |
Output is correct |
33 |
Correct |
97 ms |
27020 KB |
Output is correct |
34 |
Correct |
235 ms |
45152 KB |
Output is correct |
35 |
Correct |
165 ms |
38848 KB |
Output is correct |
36 |
Correct |
211 ms |
45140 KB |
Output is correct |
37 |
Correct |
228 ms |
46916 KB |
Output is correct |
38 |
Correct |
216 ms |
48848 KB |
Output is correct |
39 |
Correct |
91 ms |
25696 KB |
Output is correct |
40 |
Correct |
279 ms |
48304 KB |
Output is correct |
41 |
Correct |
271 ms |
48436 KB |
Output is correct |
42 |
Correct |
328 ms |
58488 KB |
Output is correct |
43 |
Correct |
103 ms |
36304 KB |
Output is correct |
44 |
Correct |
184 ms |
35940 KB |
Output is correct |
45 |
Correct |
249 ms |
46708 KB |
Output is correct |
46 |
Correct |
219 ms |
46412 KB |
Output is correct |
47 |
Correct |
236 ms |
47028 KB |
Output is correct |
48 |
Correct |
783 ms |
77108 KB |
Output is correct |