#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
typedef pair<int,int>pi;
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
void IO() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
//--------------------------------
void ckmin(int &x, int y){x=min(x,y);}
const int INF=1e9+100;
const int MX=5e4+10;
int N,M,U[MX],V[MX],W[MX],C[MX];
vector<pair<pi,int>>adj[MX];
void build(int m){
FOR(i,1,N+1) adj[i].clear();
FOR(i,0,M){
int u=U[i],v=V[i],w=W[i];
if(m) swap(u,v);
adj[u].pb({{v,w},i});
}
}
int dist[MX],par[MX],par_idx[MX];
int fu=-1,fv=-1,fidx=-1;
void dijkstra(int s){
FOR(i,1,N+1) dist[i]=INF;
dist[s]=0;
priority_queue<pi,vector<pi>,greater<pi>>q;
q.push({0,s});
while(sz(q)){
int u=q.top().se,d=q.top().fi;
q.pop();
if(d>dist[u]) continue;
for(auto it: adj[u]){
int v=it.fi.fi,w=it.fi.se,idx=it.se;
if(!(fu==u && fv==v && fidx==idx) && dist[v]>d+w){
dist[v]=d+w;
par[v]=u;
par_idx[v]=idx;
q.push({dist[v],v});
}
}
}
}
vi chosen(MX,0);
int to1[MX],toN[MX],from1[MX],fromN[MX];
void precompute(){
build(0);
dijkstra(1);
FOR(i,1,N+1) from1[i]=dist[i];
int u=N;
while(dist[N]!=INF && u!=1){
chosen[par_idx[u]]=1;
u=par[u];
}
dijkstra(N);
FOR(i,1,N+1) fromN[i]=dist[i];
u=1;
while(dist[1]!=INF && u!=N){
chosen[par_idx[u]]=1;
u=par[u];
}
build(1);
dijkstra(1);
FOR(i,1,N+1) to1[i]=dist[i];
dijkstra(N);
FOR(i,1,N+1) toN[i]=dist[i];
}
int main(){
IO();
cin>>N>>M;
FOR(i,0,M) cin>>U[i]>>V[i]>>W[i]>>C[i];
precompute();
int ans=2e9;
if(toN[1]!=INF && to1[N]!=INF) ans=toN[1]+to1[N];
build(0);
FOR(i,0,M){
if(chosen[i]){
adj[V[i]].pb({{U[i],W[i]},i});
fu=U[i],fv=V[i],fidx=i;
int x=C[i];
dijkstra(1);
if(dist[N]!=INF){
x+=dist[N];
dijkstra(N);
if(dist[1]!=INF){
x+=dist[1];
ckmin(ans,x);
}
}
adj[V[i]].pop_back();
fu=-1; fv=-1;
}
else{
int u=U[i],v=V[i];
swap(u,v);
bool c1=(max(max(from1[u],toN[v]),fromN[1])!=INF),
c2=(max(max(from1[N],to1[v]),fromN[u])!=INF),
c3=(max(max(from1[u],toN[v]),max(fromN[u],to1[v]))!=INF);
if(c1)
ckmin(ans,from1[u]+W[i]+C[i]+toN[v]+fromN[1]);
if(c2)
ckmin(ans,from1[N]+fromN[u]+C[i]+W[i]+to1[v]);
if(c3)
ckmin(ans,from1[u]+W[i]+C[i]+toN[v]+fromN[u]+W[i]+to1[v]);
}
}
if(ans>=2e9) ans=-1;
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1740 KB |
Output is correct |
2 |
Correct |
2 ms |
1740 KB |
Output is correct |
3 |
Correct |
3 ms |
1740 KB |
Output is correct |
4 |
Correct |
3 ms |
1740 KB |
Output is correct |
5 |
Correct |
3 ms |
1740 KB |
Output is correct |
6 |
Correct |
2 ms |
1740 KB |
Output is correct |
7 |
Correct |
1 ms |
1612 KB |
Output is correct |
8 |
Correct |
1 ms |
1612 KB |
Output is correct |
9 |
Correct |
3 ms |
1716 KB |
Output is correct |
10 |
Correct |
19 ms |
1740 KB |
Output is correct |
11 |
Correct |
25 ms |
1740 KB |
Output is correct |
12 |
Correct |
24 ms |
1740 KB |
Output is correct |
13 |
Correct |
3 ms |
1740 KB |
Output is correct |
14 |
Correct |
3 ms |
1740 KB |
Output is correct |
15 |
Correct |
3 ms |
1740 KB |
Output is correct |
16 |
Correct |
3 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
3728 KB |
Output is correct |
2 |
Correct |
64 ms |
3652 KB |
Output is correct |
3 |
Correct |
71 ms |
3656 KB |
Output is correct |
4 |
Correct |
4 ms |
1740 KB |
Output is correct |
5 |
Correct |
4 ms |
1740 KB |
Output is correct |
6 |
Correct |
2 ms |
1740 KB |
Output is correct |
7 |
Correct |
2 ms |
1740 KB |
Output is correct |
8 |
Correct |
1 ms |
1612 KB |
Output is correct |
9 |
Correct |
67 ms |
3836 KB |
Output is correct |
10 |
Correct |
72 ms |
3772 KB |
Output is correct |
11 |
Correct |
69 ms |
3596 KB |
Output is correct |
12 |
Correct |
70 ms |
3768 KB |
Output is correct |
13 |
Correct |
68 ms |
3572 KB |
Output is correct |
14 |
Correct |
69 ms |
3540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1740 KB |
Output is correct |
2 |
Correct |
2 ms |
1740 KB |
Output is correct |
3 |
Correct |
48 ms |
2992 KB |
Output is correct |
4 |
Correct |
2 ms |
1740 KB |
Output is correct |
5 |
Correct |
62 ms |
3576 KB |
Output is correct |
6 |
Correct |
1 ms |
1612 KB |
Output is correct |
7 |
Correct |
1 ms |
1612 KB |
Output is correct |
8 |
Correct |
60 ms |
3816 KB |
Output is correct |
9 |
Correct |
67 ms |
3788 KB |
Output is correct |
10 |
Correct |
60 ms |
3524 KB |
Output is correct |
11 |
Correct |
61 ms |
3524 KB |
Output is correct |
12 |
Correct |
67 ms |
3560 KB |
Output is correct |
13 |
Correct |
1 ms |
1612 KB |
Output is correct |
14 |
Correct |
1 ms |
1612 KB |
Output is correct |
15 |
Correct |
1 ms |
1612 KB |
Output is correct |
16 |
Correct |
2 ms |
1612 KB |
Output is correct |
17 |
Correct |
1 ms |
1688 KB |
Output is correct |
18 |
Correct |
2 ms |
1612 KB |
Output is correct |
19 |
Correct |
60 ms |
3480 KB |
Output is correct |
20 |
Correct |
60 ms |
3520 KB |
Output is correct |
21 |
Correct |
64 ms |
3480 KB |
Output is correct |
22 |
Correct |
60 ms |
3600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1740 KB |
Output is correct |
2 |
Correct |
2 ms |
1740 KB |
Output is correct |
3 |
Correct |
3 ms |
1740 KB |
Output is correct |
4 |
Correct |
3 ms |
1740 KB |
Output is correct |
5 |
Correct |
3 ms |
1740 KB |
Output is correct |
6 |
Correct |
2 ms |
1740 KB |
Output is correct |
7 |
Correct |
1 ms |
1612 KB |
Output is correct |
8 |
Correct |
1 ms |
1612 KB |
Output is correct |
9 |
Correct |
3 ms |
1716 KB |
Output is correct |
10 |
Correct |
19 ms |
1740 KB |
Output is correct |
11 |
Correct |
25 ms |
1740 KB |
Output is correct |
12 |
Correct |
24 ms |
1740 KB |
Output is correct |
13 |
Correct |
3 ms |
1740 KB |
Output is correct |
14 |
Correct |
3 ms |
1740 KB |
Output is correct |
15 |
Correct |
3 ms |
1740 KB |
Output is correct |
16 |
Correct |
3 ms |
1740 KB |
Output is correct |
17 |
Correct |
66 ms |
3728 KB |
Output is correct |
18 |
Correct |
64 ms |
3652 KB |
Output is correct |
19 |
Correct |
71 ms |
3656 KB |
Output is correct |
20 |
Correct |
4 ms |
1740 KB |
Output is correct |
21 |
Correct |
4 ms |
1740 KB |
Output is correct |
22 |
Correct |
2 ms |
1740 KB |
Output is correct |
23 |
Correct |
2 ms |
1740 KB |
Output is correct |
24 |
Correct |
1 ms |
1612 KB |
Output is correct |
25 |
Correct |
67 ms |
3836 KB |
Output is correct |
26 |
Correct |
72 ms |
3772 KB |
Output is correct |
27 |
Correct |
69 ms |
3596 KB |
Output is correct |
28 |
Correct |
70 ms |
3768 KB |
Output is correct |
29 |
Correct |
68 ms |
3572 KB |
Output is correct |
30 |
Correct |
69 ms |
3540 KB |
Output is correct |
31 |
Correct |
3 ms |
1740 KB |
Output is correct |
32 |
Correct |
2 ms |
1740 KB |
Output is correct |
33 |
Correct |
48 ms |
2992 KB |
Output is correct |
34 |
Correct |
2 ms |
1740 KB |
Output is correct |
35 |
Correct |
62 ms |
3576 KB |
Output is correct |
36 |
Correct |
1 ms |
1612 KB |
Output is correct |
37 |
Correct |
1 ms |
1612 KB |
Output is correct |
38 |
Correct |
60 ms |
3816 KB |
Output is correct |
39 |
Correct |
67 ms |
3788 KB |
Output is correct |
40 |
Correct |
60 ms |
3524 KB |
Output is correct |
41 |
Correct |
61 ms |
3524 KB |
Output is correct |
42 |
Correct |
67 ms |
3560 KB |
Output is correct |
43 |
Correct |
1 ms |
1612 KB |
Output is correct |
44 |
Correct |
1 ms |
1612 KB |
Output is correct |
45 |
Correct |
1 ms |
1612 KB |
Output is correct |
46 |
Correct |
2 ms |
1612 KB |
Output is correct |
47 |
Correct |
1 ms |
1688 KB |
Output is correct |
48 |
Correct |
2 ms |
1612 KB |
Output is correct |
49 |
Correct |
60 ms |
3480 KB |
Output is correct |
50 |
Correct |
60 ms |
3520 KB |
Output is correct |
51 |
Correct |
64 ms |
3480 KB |
Output is correct |
52 |
Correct |
60 ms |
3600 KB |
Output is correct |
53 |
Correct |
68 ms |
3580 KB |
Output is correct |
54 |
Correct |
66 ms |
3524 KB |
Output is correct |
55 |
Correct |
67 ms |
3540 KB |
Output is correct |
56 |
Correct |
4 ms |
1740 KB |
Output is correct |
57 |
Correct |
3 ms |
1740 KB |
Output is correct |
58 |
Correct |
114 ms |
2984 KB |
Output is correct |
59 |
Correct |
130 ms |
3064 KB |
Output is correct |
60 |
Correct |
167 ms |
3148 KB |
Output is correct |
61 |
Correct |
112 ms |
3032 KB |
Output is correct |
62 |
Correct |
127 ms |
3012 KB |
Output is correct |
63 |
Correct |
177 ms |
3048 KB |
Output is correct |
64 |
Correct |
724 ms |
3692 KB |
Output is correct |
65 |
Correct |
775 ms |
3792 KB |
Output is correct |
66 |
Correct |
997 ms |
3792 KB |
Output is correct |
67 |
Correct |
51 ms |
3952 KB |
Output is correct |
68 |
Correct |
72 ms |
3788 KB |
Output is correct |
69 |
Correct |
67 ms |
3736 KB |
Output is correct |
70 |
Correct |
70 ms |
3528 KB |
Output is correct |
71 |
Correct |
70 ms |
3480 KB |
Output is correct |
72 |
Correct |
70 ms |
3596 KB |
Output is correct |
73 |
Correct |
73 ms |
3552 KB |
Output is correct |
74 |
Correct |
73 ms |
3596 KB |
Output is correct |