一个比较重要的性质：反转的边要在最短路上才会有贡献。
我们可以先跑一遍最短路，记录下整颗最短路树，然后暴力的对每一条边进行判断，反转。
我们建正反图各两个，分别以 \(1\)，\(n\) 为起点。\(n\)，\(1\) 为终点。然后对每个图跑最短路，记录下最短路树。
若不反转任何一条边，则答案为 \(1\) 到 \(n\) 再到 \(1\) 的最短路。
然后暴力枚举边，第 \(i\) 条边，考虑将其反转。反转之后 \(1\) 到 \(n\) 的最短路即为 \(1\) 到 \(V_i\) 再从 \(U_i\) 走到 \(n\) 的最短路。往返分开来算。
有一个需要注意的点是，不可以开全局 long long 进行运算，否则只有 5 分。
讲的比较少，都在代码里。
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+7;
const int M=207;
int n,m;
int u[N],v[N];
long long c[N],d[N],ans;
struct node{
int frnt;
long long sum1[M],sum2[M];
bool fl[M],st[N];
int lst[N];
struct Map{
int to,val,nxt,hed;
}G[N];
int cnt=0;
void add(int u,int v,int w){
G[++cnt].to=v;
G[cnt].val=w;
G[cnt].nxt=G[u].hed;
G[u].hed=cnt;
}
void DJ(){
memset(fl,0,sizeof fl);
for(int i=1;i<=n+1;i++) sum1[i]=1e9;
sum1[frnt]=0;
for(int i=1;i<=n;i++){
int u=n+1;
for(int j=1;j<=n;j++) if(!fl[j]&&sum1[j]<sum1[u]) u=j;
if(u==n+1) break;
fl[u]=1;
for(int j=G[u].hed;j;j=G[j].nxt){
int v=G[j].to,w=G[j].val;
if(!fl[v]&&sum1[v]>sum1[u]+w){
sum1[v]=sum1[u]+w;
lst[v]=j;//给在最短路树上的点打标记。
}
}
}
for(int i=1;i<=n;i++) if(i!=frnt) st[lst[i]]=1;//这里是计录下最短路树。
}
int swp;
void DJ2(){
memset(fl,0,sizeof fl);
for(int i=1;i<=n+1;i++) sum2[i]=1e9;
sum2[frnt]=0;
for(int i=1;i<=n;i++){
int u=n+1;
for(int j=1;j<=n;j++) if(!fl[j]&&sum2[j]<sum2[u]) u=j;
if(u==n+1) break;
fl[u]=1;
for(int j=G[u].hed;j;j=G[j].nxt){
int v=G[j].to,w=G[j].val;
if(!fl[v]&&sum2[v]>sum2[u]+w&&j!=swp){//这里多了一个判断：即不能为翻转之前的边。
sum2[v]=sum2[u]+w;
}
}
}
}
long long work(int u,int end){
if(!st[u]) return sum1[end];//不在最短路树上
swp=u;
DJ2();
return sum2[end];
}
}g[5];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
g[1].frnt=g[4].frnt=1,g[2].frnt=g[3].frnt=n;
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i]>>c[i]>>d[i];
g[1].add(u[i],v[i],c[i]);//四个图
g[2].add(v[i],u[i],c[i]);
g[3].add(u[i],v[i],c[i]);
g[4].add(v[i],u[i],c[i]);
}
for(int i=1;i<=4;i++) g[i].DJ();//不反转，求最短路
ans=g[1].sum1[n]+g[3].sum1[1];//初始答案
for(int i=1;i<=m;i++){//将边反转
int go=min(g[1].work(i,n),g[1].work(i,v[i])+c[i]+g[2].work(i,u[i]));//去
int back=min(g[3].work(i,1),g[3].work(i,v[i])+c[i]+g[4].work(i,u[i]));//来
ans=min(ans,go+back+d[i]);
}
if(ans>=1e9) ans=-1;
cout<<ans;
return 0;
}