自动搬运

查看原文

来自洛谷，原作者为

	浅色调 **

搬运于2025-08-24 22:01:55，当前版本为作者最后更新于2018-09-05 11:17:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution：

本题最短路+dp。

我们先用floyd预处理出$w[i][j]$，表示$i\rightarrow j$经过的最少点数（除了i点）。

由于要求$1\rightarrow 2\rightarrow 1$经过的最少点数，而模型是个有向图，考虑dp，定义状态$f[i][j]$表示$1\rightarrow i\rightarrow j\rightarrow 1$经过的最少点数，初始化$f[1][1]=1$，状态转移方程：$f[x][y]=min(f[x][y],f[a][b]+w[b][x]+w[x][y]+w[y][a]-1)$（注意-1是因为a被多算了1次），直接dp显然是有后效性的，注意到每次由小的点对更新状态肯定最优，于是状态转移时套用堆优化dijkstra，用全局最小值$f[a][b]$去更新状态就好了。

转移时还需注意不能用点对$f[a][b]$更新自己（当a==b时直接RE）。

最坏时间复杂度$O(n^3\log n)$

$\quad\;\;$欢迎来踩博客：five20（蒟蒻写题解不易，转载请注明出处，万分感谢！～）

代码：

    /*Code by 520 -- 9.4*/
    #include<bits/stdc++.h>
    #include<ext/pb_ds/assoc_container.hpp>
    #include<ext/pb_ds/priority_queue.hpp>
    #define il inline
    #define ll long long
    #define RE register
    #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
    #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
    using namespace std;
    using namespace __gnu_pbds;
    const int N=205,inf=233333333;
    int n,m,w[N][N],dis[N][N];
    struct node{
        int u,v,d;
        bool operator<(const node &a)const{
            if(d==a.d&&u==a.u)return v>a.v;
            if(d==a.d)return u>a.u;
            return d>a.d;
        }
    };
    typedef __gnu_pbds::priority_queue<node,less<node>,pairing_heap_tag> heap;
    heap q;
    heap::point_iterator id[N][N];
    int main(){
        scanf("%d%d",&n,&m);
        For(i,1,n) For(j,1,n) w[i][j]=i==j?0:inf,dis[i][j]=inf;
        int u,v;
        while(m--) scanf("%d%d",&u,&v),w[u][v]=1;
        For(k,1,n) For(i,1,n) For(j,1,n) w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
        dis[1][1]=1,id[1][1]=q.push(node{1,1,dis[1][1]});
        while(1){
            node x=q.top();
            int a=x.u,b=x.v;q.pop();
            if(a==2&&b==2)break;
            For(c,1,n) For(d,1,n) {
                if(a==c&&b==d)continue;
                if(dis[a][b]+w[b][c]+w[c][d]+w[d][a]-1<dis[c][d]){
                    dis[c][d]=dis[a][b]+w[b][c]+w[c][d]+w[d][a]-1;
                    if(id[c][d]==0)id[c][d]=q.push(node{c,d,dis[c][d]});
                    else q.modify(id[c][d],node{c,d,dis[c][d]});
                }
            }
        }
        cout<<dis[2][2];    
        return 0;
    }