[HOJ 199][COI 2012]KAMPANJA

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

我看了CBD的題解才知道怎麼處理重複走的路徑
不過來推出的定義不太一樣，請容我修改一下方便理解(以下部分內容擷取自原文)
考慮DP[a][b]代表從1走到A加上從B走回1的路上最少可以經過幾個節點(為了方便轉移，如果A=B，A點「算兩次」)，那麼所求的答案就是DP[2][2]
首先我們可以用Floyd求出任兩點之間的最短路(之後記為DIST[][])
由第一個範測可以觀察到：
如果我們任取四個點a,b,x,y
DP[x][y]的定義為1->x和y->1路徑的最小總點數
可以用1->a->b->x和y->a->b->1這兩條路徑來更新
也就是說DP[x][y]可以用DP[a][b]+(DIST[a][b]-1)+DIST[b][x]+DIST[y][a]來更新
因此我們可以用SPFA來做這樣的更新，一開始DP全部初始化為INF，唯獨DP[1][1]=2
然後將(1,1)這個點加進queue，去鬆弛其他點，只有被鬆弛而且不在queue裡面的點才加進queue裡面
SPFA理論複雜度最差為O(VE)，上述狀態表示方式有N^2個點、N^4條邊，因此複雜度O(N^6)
但一般情況下每個點平均進出queue兩次，所以執行時間趨近O(N^4)
感覺測資再出硬一點就TLE了=ㄦ=

code:

#include<cstdio>
#include<vector>
#include<queue>
#include<cassert>
using namespace std;
const int INF=2147483647;
void getmin(int &a,const int b){if(b<a)a=b;}
int N,M,DIST[100][100],DP[100][100];
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<N;i++)for(int j=0;j<N;j++)DIST[i][j]=DP[i][j]=INF;
        for(int i=0;i<N;i++)DIST[i][i]=0;
        for(int i=0,a,b;i<M;i++)scanf("%d%d",&a,&b),a--,b--,getmin(DIST[a][b],1);
        for(int m=0;m<N;m++)
        {
            for(int a=0;a<N;a++)if(DIST[a][m]!=INF)
            {
                for(int b=0;b<N;b++)if(DIST[m][b]!=INF)getmin(DIST[a][b],DIST[a][m]+DIST[m][b]);
            }
        }
        static bool inq[100][100];
        for(int i=0;i<N;i++)for(int j=0;j<N;j++)inq[i][j]=false;
        queue<int>qa,qb;
        DP[0][0]=2,qa.push(0),qb.push(0),inq[0][0]=true;
        while(!qa.empty())
        {
            const int a=qa.front(),b=qb.front();
            qa.pop(),qb.pop();
            inq[a][b]=false;
            if(DIST[a][b]==INF)continue;
            for(int nxta=0;nxta<N;nxta++)if(DIST[b][nxta]!=INF)
            {
                for(int nxtb=0;nxtb<N;nxtb++)if(DIST[nxtb][a]!=INF)
                {
                    if(nxta==a&&nxtb==b)continue;
                    const int update=DP[a][b]+(DIST[a][b]-1)+DIST[b][nxta]+DIST[nxtb][a];
                    if(DP[nxta][nxtb]>update)
                    {
                        DP[nxta][nxtb]=update;
                        if(!inq[nxta][nxtb])qa.push(nxta),qb.push(nxtb),inq[nxta][nxtb]=true;
                    }
                }
            }
        }
        assert(DP[1][1]!=INF);
        printf("%d\n",DP[1][1]-1);
    }
    return 0;
}