「JOI 2020 Final」奥运公交 (最短路)

问题实际上就是要分别求$1-n$和$n-1$对于每一条边翻转之后的最短路

由于$m$的上限为$n^2$，下面所说的$\text{Dijkstra}$都是没有堆优化的板本，即$n^2$找最小点，$m$更新

以计算$1-n$为例

不妨先考虑计算删除每一条边$(u,v,c)$之后，1为源点的的最短路情况

我们知道从源点$S$出发的最短路可以用最短路图描述，而最短路图是一张拓扑图（fix:这道题含有0边，所以并不是，但是没有关系）

如果从最短路图中提取一棵树，那么显然只有这些树边需要考虑删除之后对于最短路的影响

对于这些边重新求最短路即可，复杂度为$O(n(m+n^2))$

如何考虑翻转一条边之后的贡献？

不妨再求出以$n$为结束的最短路，即求反图$n$为源点的答案

然后在两个最短路上查询一下即可得到$1-n$的最短路

同理得到$n-1$的答案

复杂度为$O(n(m+n^2))$

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]){ 
    // 计算删除每条边之后，S为源点的最短路情况，放在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(){ 
	//fprintf(stderr,"%.2lf\n",(&Med-&Mbe)/1024.0/1024.0);
	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];
	
    // 计算1-n
	Solve();
    // 计算n-1
	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);
}