题解 P6880 【[JOI 2020 Final] オリンピックバス】

· · 题解

题意：给你一个有向图，问你能否通过换边从1 到 n ，并使代价最小。

首先：我们肯定是枚举转换的边，然后求转换后的最短路。 但这样的复杂度是 O(n^2m) 的，因为这样会多做很多的无用功。

注意到在最短路树上的边才有可能修改后对最短路有影响，所以我们最多只用跑 O(n) 次最短路，复杂度 O(n^3) 。

最后说一下，因为我们要求 1 到 n 和 n 到 1 的最短路，我们就可以用 4 个最短路， 原点为 1 ，正图， 原点为 1 ，反图， 原点为 n ，正图，和原点为 n ，反图。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<cstdio>
#include<cstring>
#define N 205
#define M 50005
#define ll long long
using namespace std;
int n,m,x[M],y[M],c[M],d[M];
struct Graph {
    int s,n,B,vis[N],h[N];
    int las[N],pd[M],cnt;
    ll d1[N],d2[N];
    struct node {
        int to,next,value;
    } e[M];
    void Addedge(int x,int y,int z) {
        e[++cnt]=(node) {y,h[x],z},h[x]=cnt;
    }
    void Dijkstra() {
        memset(d1,0x3f,sizeof(ll)*(n+2));
        memset(vis,0,sizeof(int)*(n+1)),d1[s]=0;
        for(int i=1,j,k=n+1,y; i<=n; ++i,k=n+1) {
            for(j=1; j<=n; ++j)if(!vis[j]&&d1[j]<d1[k])k=j;
            if(k==n+1)break;
            for(j=h[k],vis[k]=1; j; j=e[j].next)if(!vis[y=e[j].to]&&d1[y]>d1[k]+e[j].value)d1[y]=d1[k]+e[j].value,las[y]=j;
        }
        for(int i=1; i<=n; ++i)if(i!=s)pd[las[i]]=1;
    }
    void Solve() {
        memset(d2,0x3f,sizeof(ll)*(n+2));
        memset(vis,0,sizeof(int)*(n+1)),d2[s]=0;
        for(int i=1,j,k=n+1,y; i<=n; ++i,k=n+1) {
            for(j=1; j<=n; ++j)if(!vis[j]&&d2[j]<d2[k])k=j;
            if(k==n+1)break;
            for(j=h[k],vis[k]=1; j; j=e[j].next)if(!vis[y=e[j].to]&&B!=j&&d2[y]>d2[k]+e[j].value)d2[y]=d2[k]+e[j].value;
        }
    }
    ll Calc(int x,int y) {
        if(!pd[x])return d1[y];
        return (B!=x?(B=x,Solve()):void()),d2[y];
    }
} G[4];
inline int read() {
    int s=0,f=0;
    char ch=getchar();
    while(ch<48||ch>57)f=(ch=='-'),ch=getchar();
    while(ch>47&&ch<58)s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return f?-s:s;
}
ll min(ll x,ll y) {
    return x<y?x:y;
}
int main() {
    n=read(),m=read(),G[0].s=G[2].s=1,G[1].s=G[3].s=n,G[0].n=G[2].n=G[1].n=G[3].n=n;
    for(int i=1; i<=m; ++i) {
        x[i]=read(),y[i]=read(),c[i]=read(),d[i]=read();
        G[0].Addedge(x[i],y[i],c[i]),G[1].Addedge(y[i],x[i],c[i]);//1->i,i->n
        G[2].Addedge(y[i],x[i],c[i]),G[3].Addedge(x[i],y[i],c[i]);//i->1,n->i
    }
    for(int i=0; i<4; ++i)G[i].Dijkstra();
    ll ans=G[0].d1[n]+G[3].d1[1];
    for(int i=1; i<=m; ++i) {
        ll dn=min(G[0].Calc(i,n),G[0].Calc(i,y[i])+c[i]+G[1].Calc(i,x[i]));
        ll d1=min(G[3].Calc(i,1),G[3].Calc(i,y[i])+c[i]+G[2].Calc(i,x[i]));
        ans=min(ans,d1+dn+d[i]);
    }
    printf("%lld",(ans<1e17)?ans:-1);
    return 0;
}