「JOI 2020 Final」奥运公交
Description
Input
Output
Sample Input
样例 1 输入：
4 5
1 2 4 4
1 3 2 1
4 3 1 2
4 1 6 1
2 4 2 5
样例 2 输入：
4 10
1 2 4 4
1 2 4 4
1 3 2 1
1 3 2 1
4 3 1 2
4 3 1 2
4 1 6 1
4 1 6 1
2 4 2 5
2 4 2 5
样例 3 输入：
4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1
样例 4 输入：
4 5
1 2 4 4
1 3 2 4
4 3 1 5
4 1 6 1
2 4 2 5
样例 5 输入：
4 5
2 1 4 4
1 3 2 1
4 3 1 2
4 3 6 1
2 4 2 5
Sample Output
样例1输出：
10样例2输出：
10
这个样例满足子任务 2 的限制。
样例3输出：
2
这个样例满足子任务3的限制。
样例4输出：
12
不是一定要翻转某条公交线。
样例5输出：
-1
在这个样例中，从城市4到城市3的公交线有两条。
Data Constraint
题解
看到这道题的第一眼，会很显然地想到每次枚举一条翻转的边跑最短路，但这样的复杂度显然非常的大，只能拿到最低档的5分（捆绑数据要是打炸了还一分没有）
分析一下数据范围，我们发现如果有一种\(O(n^{3})\)左右的算法就可以不多不少刚刚好跑过
首先我们明确包括一共有四种从\(1\sim n\)再从\(n\sim 1\)的走法：
- \(1\sim n\)和\(n\sim 1\)都走不用经过翻转的边的最短路
- \(1\sim n\)走必经过翻转的边\(v\sim u\)的最短路，\(n\sim 1\)走不用经过翻转的边的最短路
- \(1\sim n\)走不用经过翻转的边的最短路，\(n\sim 1\)走必经过翻转的边\(v\sim u\)的最短路
- \(1\sim n\)和\(n\sim 1\)都走必经过翻转的边\(v\sim u\)的最短路
（有点绕口）
再想想我们需要在没有任何边翻转的原图中先得到那些东西：
- 1号城市到\(n\)号个城市的最短路
- \(n\)号城市到1号城市的最短路
- 每个城市到1号城市的最短路
- 每个城市到\(n\)号城市的最短路
前两个直接在原图跑最短路，后两个建个反图跑最短路即可
至于为什么要建反图，是因为如果你把某条边翻转了之后，原先有在最短中的边就不存在了，所以不能直接从前两个的结果中赋值过来（还是不懂的可以画图手动模拟一下，很显然是不相同的）（那你说了那么多，还不是要枚举每条边去翻转？？？）
对于翻转操作，我们有一个奇技淫巧好的方法进行处理：因为如果我们没有翻转在\(1\sim n\)和\(n\sim 1\)最短路上的边，上述第一中走法中是不会产生贡献的，而在最短路上的边翻转之后，对于我们当前求出的其他走法中也不会更优
所以我们只需要在跑前两遍最短路时处理出在\(1\sim n\)和\(n\sim 1\)最短路上的边，然后枚举这些边，暴力加边跑最短路，做第一种走法，其它的边就直接\(O(1)\)走后面三种走法，然后判断取最小值即可
然后我们就可以限制枚举边翻转的复杂度在严格\(O(n)\)以内了
实现有亿一点点细节，但是明确思路之后就不难写
CODE
#include<cstdio>
#include<string>
#define R register int
#define N 205
#define M 50005
#define ll long long
#define inf 1234567891011
using namespace std;
struct G{ll to,next,id;ll w;}e[M];
int n,m,u[M],v[M],cnt,head[N],nxt[N],last[N];
ll c[M],d[M],ans1,ans2,ans,dist1[N],dist2[N][5];
bool bz[N],flag[M];
ll min(ll a,ll b) {return a<b?a:b;}
void read(int &x)
{
x=0;ll f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch==‘-‘) f=-1;ch=getchar();}
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
void read1(ll &x)
{
x=0;ll f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch==‘-‘) f=-1;ch=getchar();}
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
void add(int u,int v,ll w,int id)
{
e[++cnt].to=v;e[cnt].w=w;e[cnt].id=id;
e[cnt].next=head[u];head[u]=cnt;
}
void dij1(int s)
{
for (R i=1;i<=n;++i) dist1[i]=inf,bz[i]=0,nxt[i]=0;
dist1[s]=0;
for (R i=1;i<=n;++i)
{
ll mn=inf;int k=n+1;
for (R j=1;j<=n;++j) if (!bz[j] && dist1[j]<mn) mn=dist1[j],k=j;
if (k==n+1) break;bz[k]=1;
for (R j=head[k];j;j=e[j].next)
{
int v=e[j].to;
if (dist1[v]>dist1[k]+e[j].w) dist1[v]=dist1[k]+e[j].w,nxt[v]=k,last[v]=j;
}
}
}
void dij2(int s,int num)
{
for (R i=1;i<=n;++i) dist2[i][num]=inf,bz[i]=0;
dist2[s][num]=0;
for (R i=1;i<=n;++i)
{
ll mn=inf;int k=n+1;
for (R j=1;j<=n;++j) if (!bz[j] && dist2[j][num]<mn) mn=dist2[j][num],k=j;
if (k==n+1) break;bz[k]=1;
for (R j=head[k];j;j=e[j].next)
{
int v=e[j].to;
if (dist2[v][num]>dist2[k][num]+e[j].w) dist2[v][num]=dist2[k][num]+e[j].w;
}
}
}
void build(ll u)
{
while (u) flag[last[u]]=1,u=nxt[u];
}
int main()
{
read(n);read(m);
for (R i=1;i<=m;++i)
{
read(u[i]);read(v[i]);read1(c[i]);read1(d[i]);
add(u[i],v[i],c[i],i);
}
dij1(1);ans1=dist1[n];build(n);
dij1(n);ans2=dist1[1];build(1);ans=ans1+ans2;
dij2(1,1);dij2(n,2);
for (R i=1;i<=n;++i) head[i]=0;cnt=0;
for (R i=1;i<=m;++i) add(v[i],u[i],c[i],i);
dij2(1,3);dij2(n,4);
for (R i=1;i<=m;++i)
{
if (flag[i])
{
for (R j=1;j<=n;++j) head[j]=0;cnt=0;
for (R j=1;j<=m;++j)
if (j==i) add(v[j],u[j],c[j],j);else add(u[j],v[j],c[j],j);
dij1(1);ll tot1=dist1[n];dij1(n);ll tot2=dist1[1];ans=min(ans,tot1+d[i]+tot2);
}
else
{
ans=min(ans,ans1+dist2[v[i]][2]+c[i]+d[i]+dist2[u[i]][3]);
ans=min(ans,ans2+dist2[v[i]][1]+c[i]+d[i]+dist2[u[i]][4]);
ans=min(ans,dist2[v[i]][1]+c[i]+d[i]+dist2[u[i]][4]+dist2[v[i]][2]+c[i]+dist2[u[i]][3]);
}
}
if (ans>=inf) printf("-1\n");else printf("%lld\n",ans);
return 0;
}