#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];
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)){
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 |
104 ms |
19292 KB |
Output is correct |
2 |
Correct |
4 ms |
19036 KB |
Output is correct |
3 |
Correct |
6 ms |
19292 KB |
Output is correct |
4 |
Correct |
7 ms |
19292 KB |
Output is correct |
5 |
Correct |
5 ms |
19292 KB |
Output is correct |
6 |
Correct |
4 ms |
19292 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
5 ms |
19292 KB |
Output is correct |
10 |
Correct |
40 ms |
19316 KB |
Output is correct |
11 |
Correct |
52 ms |
19292 KB |
Output is correct |
12 |
Correct |
55 ms |
19292 KB |
Output is correct |
13 |
Correct |
4 ms |
19292 KB |
Output is correct |
14 |
Correct |
6 ms |
19328 KB |
Output is correct |
15 |
Correct |
7 ms |
19292 KB |
Output is correct |
16 |
Correct |
6 ms |
19292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
20692 KB |
Output is correct |
2 |
Correct |
26 ms |
20628 KB |
Output is correct |
3 |
Correct |
26 ms |
20692 KB |
Output is correct |
4 |
Correct |
7 ms |
19360 KB |
Output is correct |
5 |
Correct |
10 ms |
19312 KB |
Output is correct |
6 |
Correct |
6 ms |
19288 KB |
Output is correct |
7 |
Correct |
4 ms |
19292 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
17 ms |
20560 KB |
Output is correct |
10 |
Correct |
21 ms |
20656 KB |
Output is correct |
11 |
Correct |
28 ms |
20564 KB |
Output is correct |
12 |
Correct |
25 ms |
20688 KB |
Output is correct |
13 |
Correct |
25 ms |
21828 KB |
Output is correct |
14 |
Correct |
29 ms |
21956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
19292 KB |
Output is correct |
2 |
Correct |
11 ms |
19288 KB |
Output is correct |
3 |
Execution timed out |
1044 ms |
20692 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
104 ms |
19292 KB |
Output is correct |
2 |
Correct |
4 ms |
19036 KB |
Output is correct |
3 |
Correct |
6 ms |
19292 KB |
Output is correct |
4 |
Correct |
7 ms |
19292 KB |
Output is correct |
5 |
Correct |
5 ms |
19292 KB |
Output is correct |
6 |
Correct |
4 ms |
19292 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
5 ms |
19292 KB |
Output is correct |
10 |
Correct |
40 ms |
19316 KB |
Output is correct |
11 |
Correct |
52 ms |
19292 KB |
Output is correct |
12 |
Correct |
55 ms |
19292 KB |
Output is correct |
13 |
Correct |
4 ms |
19292 KB |
Output is correct |
14 |
Correct |
6 ms |
19328 KB |
Output is correct |
15 |
Correct |
7 ms |
19292 KB |
Output is correct |
16 |
Correct |
6 ms |
19292 KB |
Output is correct |
17 |
Correct |
26 ms |
20692 KB |
Output is correct |
18 |
Correct |
26 ms |
20628 KB |
Output is correct |
19 |
Correct |
26 ms |
20692 KB |
Output is correct |
20 |
Correct |
7 ms |
19360 KB |
Output is correct |
21 |
Correct |
10 ms |
19312 KB |
Output is correct |
22 |
Correct |
6 ms |
19288 KB |
Output is correct |
23 |
Correct |
4 ms |
19292 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
17 ms |
20560 KB |
Output is correct |
26 |
Correct |
21 ms |
20656 KB |
Output is correct |
27 |
Correct |
28 ms |
20564 KB |
Output is correct |
28 |
Correct |
25 ms |
20688 KB |
Output is correct |
29 |
Correct |
25 ms |
21828 KB |
Output is correct |
30 |
Correct |
29 ms |
21956 KB |
Output is correct |
31 |
Correct |
106 ms |
19292 KB |
Output is correct |
32 |
Correct |
11 ms |
19288 KB |
Output is correct |
33 |
Execution timed out |
1044 ms |
20692 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |