题解：AT_joi2020ho_d オリンピックバス (Olympic Bus)

ev_____ · 2026-07-24 10:22:18 · 题解

发现这是个 n \le 200 的稠密图，所以求最短路不能用堆优化，要用 O(n^2) 的朴素 Dijkstra。

对于图中的一条边 edge_i，有这两种情况：

枚举 m 条边并分别计算即可。 ::::success[code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,INF=1e18;
vector<array<int,4>> e[N];
int vis[210],n,m;
int spos,tmpd[210];
int mp[3][N],dist[210][210],to[210];
void dij(int s,int ops,int dis[]){
    for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=to[i]=0;
    dis[s]=0;
    for(int i=1;i<=n;i++){ 
        int u=-1;
        for(int j=1;j<=n;j++) if(!vis[j]&&(u==-1||dis[j]<dis[u])) u=j;
        vis[u]=1;
        for(auto [v,c,pos,flg]:e[u])
            if(((flg==0&&pos==spos)||(flg==1&&pos!=spos))&&!vis[v]&&dis[u]+c<dis[v])
                dis[v]=dis[u]+c,to[v]=pos;
    }
    for(int v=1;v<=n;v++) if(to[v]) mp[ops][to[v]]=1;
}
array<int,5> edge[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,c,d;cin>>u>>v>>c>>d;
        e[u].push_back({v,c,i,1});
        e[v].push_back({u,c,i,0});
        edge[i]={u,v,c,d,i};
    }
    for(int i=1;i<=n;i++){
        if(i==1) dij(1,0,dist[1]);
        else if(i==n) dij(n,1,dist[n]);
        else dij(i,2,dist[i]);
    }
    int ans=dist[1][n]+dist[n][1];
    for(int i=1;i<=m;i++){
        auto [u,v,c,d,pos]=edge[i];
        int nd1,nd2;
        if(mp[0][pos]) spos=i,dij(1,2,tmpd),nd1=tmpd[n];
        else nd1=min(dist[1][n],dist[1][v]+dist[u][n]+c);
        if(mp[1][pos]) spos=i,dij(n,2,tmpd),nd2=tmpd[1];
        else nd2=min(dist[n][1],dist[n][v]+dist[u][1]+c);
        ans=min(ans,nd1+nd2+d);
    }
    cout<<((ans>=INF)?-1:ans);
    return 0;
}

::::