[HOJ 199] KAMPANJA

作法：

考慮$d[A][B]$代表從$1$走到$A$走到$B$再走回$A$的路上最少可以經過幾個節點，那麼所求的答案就是$d[2][2]$。首先我們可以用 Floyd 求出任兩點之間的最短路（之後記為$dis[][]$），就可以先得到$d[A][B]$的一些初始值，並且由第一個範測可以觀察到：如果我們任取四個點$A,B,X,Y$，那麼$1\rightarrow X\rightarrow Y\rightarrow 1$實際上可以用$1\rightarrow  A\rightarrow  B\rightarrow  X\rightarrow  Y\rightarrow  A\rightarrow  B\rightarrow  1$來達成，也就是我們可以用$d[A][B]+dis[B][X]+dis[X][Y]+dis[Y][A]-1$來更新$d[X][Y]$的值。注意到上式中當$X,Y,A,B$不全相等時，$dis[B][X]+dis[X][Y]+dis[Y][A]-1\geq 0$，這就類似在求最短路的過程，因此我們可以直接套用 Dijkstra 求得答案。注意到這裡的 Dijkstra 不是用 priority_queue 優化的，而是優化前的「每次掃一遍所有的節點看誰目前距離最小，拿他來鬆弛其他人」，前者複雜度會變成$O(n^4logn)$，後者則是$O(n^4)$（因為這張圖是稠密圖）。

code :

#include<bits/stdc++.h>
#define INF 1000
using namespace std;
const int maxn=100+5 ;
 
int dis[maxn][maxn] ;
int d[maxn][maxn] ;
bool done[maxn][maxn] ;
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        dis[i][j]=(i==j?0:INF) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        dis[x][y]=1 ;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        d[i][j]=min(INF,dis[1][i]+dis[i][j]+dis[j][1]) ;
    d[1][1]=1 ;
    int tot=n*n ;
    while(tot--)
    {
        int ix,iy,mi=INF+1 ;
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
            if(!done[i][j] && d[i][j]<mi)
            mi=d[i][j] , ix=i , iy=j ;
        done[ix][iy]=1 ;
        if(ix==2 && iy==2){printf("%d\n",mi) ; break ;}
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!done[i][j])
            d[i][j]=min(d[i][j],d[ix][iy]+dis[iy][i]+dis[i][j]+dis[j][ix]-1) ;
    }
}