考慮$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) ; } }
沒有留言:
張貼留言