#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int maxn = 4e5 + 5;
const ll INF = 2e9 + 7;
struct edge{
int a, b, c, d;
edge(){}
edge(int _a, int _b, int _c, int _d) : a(_a), b(_b), c(_c), d(_d){}
};
int n, m;
vector<int> adj[maxn], radj[maxn];
vector<edge> e;
int invalid[50000 + 4];
int main(void){
fastio;
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b, c, d;
cin>>a>>b>>c>>d;
a--, b--;
adj[a].pb(i);
radj[b].pb(i);
e.pb(edge(a, b, c, d));
}
vector<ll> dist(n, INF), dist2(n, INF), rdist(n, INF), rdist2(n, INF);
dist[0] = 0, dist2[n - 1] = 0, rdist[n - 1] = 0, rdist2[0] = 0;
auto dijkstra = [&](vector<ll>& dist) -> void{
vector<int> vis(n);
for(int i = 0; i < n; i++){
ll mn = INF, id = 0;
for(int j = 0; j < n; j++) if(!vis[j] && dist[j] < mn) mn = dist[j], id = j;
vis[id] = 1;
for(auto x : adj[id]){
if(invalid[x]) continue;
auto [a, b, c, d] = e[x];
dist[b] = min(dist[b], dist[a] + c);
}
}
};
auto rdijkstra = [&](vector<ll>& dist) -> void{
vector<int> vis(n);
for(int i = 0; i < n; i++){
ll mn = INF, id = 0;
for(int j = 0; j < n; j++) if(!vis[j] && dist[j] < mn) mn = dist[j], id = j;
vis[id] = 1;
for(auto x : radj[id]){
auto [a, b, c, d] = e[x];
dist[a] = min(dist[a], dist[b] + c);
}
}
};
dijkstra(dist);
dijkstra(dist2);
rdijkstra(rdist);
rdijkstra(rdist2);
ll ans = dist[n - 1] + dist2[0];
int cnt = 0;
for(int i = 0; i < m; i++){
auto [a, b, c, d] = e[i];
if((dist[a] + rdist[b] + c == dist[n - 1] && dist[n - 1] < INF) || (dist2[a] + rdist2[b] + c == dist2[0] && dist2[0] < INF)){
cnt++;
if(cnt > n * 3) break;
invalid[i] = 1;
e.pb(edge(b, a, c, d));
adj[b].pb(m);
vector<ll> ndist(n, INF), ndist2(n, INF);
ndist[0] = 0, ndist2[n - 1] = 0;
dijkstra(ndist), dijkstra(ndist2);
ans = min(ans, ndist[n - 1] + ndist2[0] + d);
e.pop_back();
adj[b].pop_back();
invalid[i] = 0;
continue;
}
//invert : becomes b->a
ll d1 = min(dist[n - 1], dist[b] + rdist[a] + c);
ll d2 = min(dist2[0], dist2[b] + rdist2[a] + c);
ans = min(ans, d1 + d2 + d);
}
cout<<(ans < INF ? ans : -1)<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
19292 KB |
Output is correct |
2 |
Correct |
4 ms |
19292 KB |
Output is correct |
3 |
Correct |
7 ms |
19324 KB |
Output is correct |
4 |
Correct |
7 ms |
19324 KB |
Output is correct |
5 |
Correct |
5 ms |
19292 KB |
Output is correct |
6 |
Correct |
4 ms |
19036 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
5 ms |
19036 KB |
Output is correct |
9 |
Correct |
4 ms |
19292 KB |
Output is correct |
10 |
Correct |
39 ms |
19316 KB |
Output is correct |
11 |
Correct |
60 ms |
19308 KB |
Output is correct |
12 |
Correct |
48 ms |
19300 KB |
Output is correct |
13 |
Correct |
4 ms |
19292 KB |
Output is correct |
14 |
Correct |
6 ms |
19324 KB |
Output is correct |
15 |
Correct |
5 ms |
19292 KB |
Output is correct |
16 |
Correct |
6 ms |
19292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
20692 KB |
Output is correct |
2 |
Correct |
26 ms |
20692 KB |
Output is correct |
3 |
Correct |
29 ms |
20748 KB |
Output is correct |
4 |
Correct |
7 ms |
19292 KB |
Output is correct |
5 |
Correct |
9 ms |
19288 KB |
Output is correct |
6 |
Correct |
4 ms |
19288 KB |
Output is correct |
7 |
Correct |
4 ms |
19196 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
17 ms |
20744 KB |
Output is correct |
10 |
Correct |
17 ms |
20556 KB |
Output is correct |
11 |
Correct |
31 ms |
20796 KB |
Output is correct |
12 |
Correct |
26 ms |
20780 KB |
Output is correct |
13 |
Correct |
26 ms |
20752 KB |
Output is correct |
14 |
Correct |
25 ms |
20692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
19292 KB |
Output is correct |
2 |
Correct |
13 ms |
19292 KB |
Output is correct |
3 |
Correct |
230 ms |
20688 KB |
Output is correct |
4 |
Correct |
4 ms |
19292 KB |
Output is correct |
5 |
Correct |
320 ms |
21552 KB |
Output is correct |
6 |
Correct |
4 ms |
19036 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
18 ms |
21444 KB |
Output is correct |
9 |
Correct |
18 ms |
21536 KB |
Output is correct |
10 |
Correct |
299 ms |
21640 KB |
Output is correct |
11 |
Correct |
265 ms |
21640 KB |
Output is correct |
12 |
Correct |
303 ms |
21684 KB |
Output is correct |
13 |
Correct |
4 ms |
19036 KB |
Output is correct |
14 |
Correct |
5 ms |
19036 KB |
Output is correct |
15 |
Correct |
4 ms |
19032 KB |
Output is correct |
16 |
Correct |
4 ms |
19036 KB |
Output is correct |
17 |
Correct |
4 ms |
19036 KB |
Output is correct |
18 |
Correct |
4 ms |
19036 KB |
Output is correct |
19 |
Incorrect |
267 ms |
21460 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
19292 KB |
Output is correct |
2 |
Correct |
4 ms |
19292 KB |
Output is correct |
3 |
Correct |
7 ms |
19324 KB |
Output is correct |
4 |
Correct |
7 ms |
19324 KB |
Output is correct |
5 |
Correct |
5 ms |
19292 KB |
Output is correct |
6 |
Correct |
4 ms |
19036 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
5 ms |
19036 KB |
Output is correct |
9 |
Correct |
4 ms |
19292 KB |
Output is correct |
10 |
Correct |
39 ms |
19316 KB |
Output is correct |
11 |
Correct |
60 ms |
19308 KB |
Output is correct |
12 |
Correct |
48 ms |
19300 KB |
Output is correct |
13 |
Correct |
4 ms |
19292 KB |
Output is correct |
14 |
Correct |
6 ms |
19324 KB |
Output is correct |
15 |
Correct |
5 ms |
19292 KB |
Output is correct |
16 |
Correct |
6 ms |
19292 KB |
Output is correct |
17 |
Correct |
25 ms |
20692 KB |
Output is correct |
18 |
Correct |
26 ms |
20692 KB |
Output is correct |
19 |
Correct |
29 ms |
20748 KB |
Output is correct |
20 |
Correct |
7 ms |
19292 KB |
Output is correct |
21 |
Correct |
9 ms |
19288 KB |
Output is correct |
22 |
Correct |
4 ms |
19288 KB |
Output is correct |
23 |
Correct |
4 ms |
19196 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
17 ms |
20744 KB |
Output is correct |
26 |
Correct |
17 ms |
20556 KB |
Output is correct |
27 |
Correct |
31 ms |
20796 KB |
Output is correct |
28 |
Correct |
26 ms |
20780 KB |
Output is correct |
29 |
Correct |
26 ms |
20752 KB |
Output is correct |
30 |
Correct |
25 ms |
20692 KB |
Output is correct |
31 |
Correct |
73 ms |
19292 KB |
Output is correct |
32 |
Correct |
13 ms |
19292 KB |
Output is correct |
33 |
Correct |
230 ms |
20688 KB |
Output is correct |
34 |
Correct |
4 ms |
19292 KB |
Output is correct |
35 |
Correct |
320 ms |
21552 KB |
Output is correct |
36 |
Correct |
4 ms |
19036 KB |
Output is correct |
37 |
Correct |
4 ms |
19036 KB |
Output is correct |
38 |
Correct |
18 ms |
21444 KB |
Output is correct |
39 |
Correct |
18 ms |
21536 KB |
Output is correct |
40 |
Correct |
299 ms |
21640 KB |
Output is correct |
41 |
Correct |
265 ms |
21640 KB |
Output is correct |
42 |
Correct |
303 ms |
21684 KB |
Output is correct |
43 |
Correct |
4 ms |
19036 KB |
Output is correct |
44 |
Correct |
5 ms |
19036 KB |
Output is correct |
45 |
Correct |
4 ms |
19032 KB |
Output is correct |
46 |
Correct |
4 ms |
19036 KB |
Output is correct |
47 |
Correct |
4 ms |
19036 KB |
Output is correct |
48 |
Correct |
4 ms |
19036 KB |
Output is correct |
49 |
Incorrect |
267 ms |
21460 KB |
Output isn't correct |
50 |
Halted |
0 ms |
0 KB |
- |