#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
int n, m;
vector<array<int, 3>> adj[100100];
vector<pair<int, ll>> G[500500];
vector<pair<int, int>> P;
ll dist[500500];
int getidx(int x, int y){
return lower_bound(P.begin(), P.end(), pair<int, int>(x, y)) - P.begin() + n + 1;
}
void dijkstra(int s, int SZ){
fill(dist+1, dist+SZ+1, INF);
dist[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.emplace(0, s);
while(!pq.empty()){
auto [d, s] = pq.top(); pq.pop();
if (d > dist[s]) continue;
assert(d == dist[s]);
for (auto &[v, w]:G[s]) if (dist[v] > dist[s] + w){
dist[v] = dist[s] + w;
pq.emplace(dist[v], v);
}
}
}
int main(){
scanf("%d %d", &n, &m);
for (int i=1;i<=m;i++){
int x, y, z, w;
scanf("%d %d %d %d", &x, &y, &z, &w);
adj[x].push_back({y, z, w});
adj[y].push_back({x, z, w});
}
for (int i=1;i<=n;i++){
sort(adj[i].begin(), adj[i].end(), [&](const array<int, 3> &x, const array<int, 3> &y){
return x[1] < y[1];
});
for (auto &x:adj[i]) P.emplace_back(i, x[1]);
}
P.erase(unique(P.begin(), P.end()), P.end());
for (int i=1;i<=n;i++){
for (int j=0,r=0;j<(int)adj[i].size();j=r){
while(r<(int)adj[i].size() && adj[i][j][1]==adj[i][r][1]) ++r;
ll S = 0;
for (int k=j;k<r;k++) S += adj[i][k][2];
int i2 = getidx(i, adj[i][j][1]);
for (int k=j;k<r;k++){
auto [v, c, w] = adj[i][k];
G[i].emplace_back(v, min((ll)w, S - w));
G[i].emplace_back(getidx(v, c), 0);
G[i2].emplace_back(v, S - w);
}
}
}
dijkstra(1, n+P.size());
printf("%lld\n", dist[n]==INF?-1:dist[n]);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d %d %d %d", &x, &y, &z, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
7 ms |
14292 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
7 ms |
14292 KB |
Output is correct |
5 |
Correct |
7 ms |
14420 KB |
Output is correct |
6 |
Correct |
8 ms |
14420 KB |
Output is correct |
7 |
Correct |
9 ms |
14504 KB |
Output is correct |
8 |
Correct |
8 ms |
14468 KB |
Output is correct |
9 |
Correct |
9 ms |
14804 KB |
Output is correct |
10 |
Correct |
10 ms |
14804 KB |
Output is correct |
11 |
Correct |
9 ms |
14780 KB |
Output is correct |
12 |
Correct |
10 ms |
14676 KB |
Output is correct |
13 |
Correct |
11 ms |
14804 KB |
Output is correct |
14 |
Correct |
11 ms |
14812 KB |
Output is correct |
15 |
Correct |
8 ms |
14504 KB |
Output is correct |
16 |
Correct |
9 ms |
14804 KB |
Output is correct |
17 |
Correct |
9 ms |
14664 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
9 ms |
14804 KB |
Output is correct |
20 |
Correct |
8 ms |
14588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
31832 KB |
Output is correct |
2 |
Correct |
57 ms |
22412 KB |
Output is correct |
3 |
Correct |
143 ms |
41784 KB |
Output is correct |
4 |
Correct |
79 ms |
26256 KB |
Output is correct |
5 |
Correct |
277 ms |
56080 KB |
Output is correct |
6 |
Correct |
254 ms |
55944 KB |
Output is correct |
7 |
Correct |
199 ms |
53620 KB |
Output is correct |
8 |
Correct |
298 ms |
53768 KB |
Output is correct |
9 |
Correct |
306 ms |
53788 KB |
Output is correct |
10 |
Correct |
195 ms |
41664 KB |
Output is correct |
11 |
Correct |
112 ms |
33728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
7 ms |
14292 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
7 ms |
14292 KB |
Output is correct |
5 |
Correct |
7 ms |
14420 KB |
Output is correct |
6 |
Correct |
8 ms |
14420 KB |
Output is correct |
7 |
Correct |
9 ms |
14504 KB |
Output is correct |
8 |
Correct |
8 ms |
14468 KB |
Output is correct |
9 |
Correct |
9 ms |
14804 KB |
Output is correct |
10 |
Correct |
10 ms |
14804 KB |
Output is correct |
11 |
Correct |
9 ms |
14780 KB |
Output is correct |
12 |
Correct |
10 ms |
14676 KB |
Output is correct |
13 |
Correct |
11 ms |
14804 KB |
Output is correct |
14 |
Correct |
11 ms |
14812 KB |
Output is correct |
15 |
Correct |
8 ms |
14504 KB |
Output is correct |
16 |
Correct |
9 ms |
14804 KB |
Output is correct |
17 |
Correct |
9 ms |
14664 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
9 ms |
14804 KB |
Output is correct |
20 |
Correct |
8 ms |
14588 KB |
Output is correct |
21 |
Correct |
119 ms |
31832 KB |
Output is correct |
22 |
Correct |
57 ms |
22412 KB |
Output is correct |
23 |
Correct |
143 ms |
41784 KB |
Output is correct |
24 |
Correct |
79 ms |
26256 KB |
Output is correct |
25 |
Correct |
277 ms |
56080 KB |
Output is correct |
26 |
Correct |
254 ms |
55944 KB |
Output is correct |
27 |
Correct |
199 ms |
53620 KB |
Output is correct |
28 |
Correct |
298 ms |
53768 KB |
Output is correct |
29 |
Correct |
306 ms |
53788 KB |
Output is correct |
30 |
Correct |
195 ms |
41664 KB |
Output is correct |
31 |
Correct |
112 ms |
33728 KB |
Output is correct |
32 |
Correct |
124 ms |
45360 KB |
Output is correct |
33 |
Correct |
136 ms |
41776 KB |
Output is correct |
34 |
Correct |
245 ms |
49028 KB |
Output is correct |
35 |
Correct |
208 ms |
43024 KB |
Output is correct |
36 |
Correct |
177 ms |
42576 KB |
Output is correct |
37 |
Correct |
205 ms |
50908 KB |
Output is correct |
38 |
Correct |
221 ms |
59460 KB |
Output is correct |
39 |
Correct |
164 ms |
55124 KB |
Output is correct |
40 |
Correct |
320 ms |
59124 KB |
Output is correct |
41 |
Correct |
352 ms |
59420 KB |
Output is correct |
42 |
Correct |
327 ms |
57924 KB |
Output is correct |
43 |
Correct |
143 ms |
36596 KB |
Output is correct |
44 |
Correct |
221 ms |
60088 KB |
Output is correct |
45 |
Correct |
249 ms |
48304 KB |
Output is correct |
46 |
Correct |
198 ms |
46316 KB |
Output is correct |
47 |
Correct |
216 ms |
47376 KB |
Output is correct |
48 |
Correct |
321 ms |
61908 KB |
Output is correct |