1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T& a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T& a,T b){ ((a<b)&&(a=b)); }
char IO;
template <class T=int> T rd(){
T s=0;int f=0;
while(!isdigit(IO=getchar())) f|=IO=='-';
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
bool Mbe;
const int N=210,M=5e4+10,INF=2e9+10;
int n,m;
int E[N][N],E2[N][N],EI[N][N],dis[N],vis[N];
void Dijkstra(int S){
rep(i,0,n) dis[i]=INF,vis[i]=0;
dis[S]=0;
while(1) {
int u=0;
rep(i,1,n) if(!vis[i] && dis[i]<dis[u]) u=i;
if(!u) break;
vis[u]=1;
rep(i,1,n) if(E[u][i]<INF) cmin(dis[i],dis[u]+E[u][i]);
}
}
int U[M],V[M],C[M],D[M];
int mk[M];
void dfs(int u) {
vis[u]=1;
rep(i,1,n) if(!vis[i] && E[u][i]<INF && dis[i]==dis[u]+E[u][i]) mk[EI[u][i]]=1,dfs(i);
}
int Res1[M][N],Res2[M][N];
ll Ans[M];
void Solve(int S,int Res[M][N]){
rep(i,1,n) rep(j,1,n) E[i][j]=INF,E2[i][j]=INF;
rep(i,1,m) {
int u=U[i],v=V[i],c=C[i];
if(E[u][v]>c) E2[u][v]=E[u][v],E[u][v]=c,EI[u][v]=i;
else if(E2[u][v]>c) E2[u][v]=c;
}
Dijkstra(S);
rep(i,1,n) vis[i]=0;
rep(i,1,m) mk[i]=0;
dfs(S);
rep(i,1,m) if(!mk[i]) rep(j,1,n) Res[i][j]=dis[j];
rep(i,1,m) if(mk[i]) {
swap(E[U[i]][V[i]],E2[U[i]][V[i]]);
Dijkstra(S);
rep(j,1,n) Res[i][j]=dis[j];
swap(E[U[i]][V[i]],E2[U[i]][V[i]]);
}
}
void Solve(){
Solve(1,Res1);
rep(i,1,m) swap(U[i],V[i]);
Solve(n,Res2);
rep(i,1,m) swap(U[i],V[i]);
rep(i,1,m) {
int t=min(Res1[i][n],Res2[i][1]);
if(Res1[i][V[i]]<INF && Res2[i][U[i]]<INF) cmin(t,Res1[i][V[i]]+Res2[i][U[i]]+C[i]);
Ans[i]+=t;
}
}
bool Med;
int main(){
n=rd(),m=rd();
rep(i,1,m) U[i]=rd(),V[i]=rd(),C[i]=rd(),D[i]=rd();
ll ans=0;
rep(i,1,n) rep(j,1,n) E[i][j]=INF;
rep(i,1,m) cmin(E[U[i]][V[i]],C[i]);
Dijkstra(1),ans+=dis[n];
Dijkstra(n),ans+=dis[1];
Solve();
rep(i,1,m) U[i]=n-U[i]+1,V[i]=n-V[i]+1;
Solve();
rep(i,1,m) cmin(ans,Ans[i]+D[i]);
printf("%lld\n",ans>=INF?-1:ans);
}
|
