BZOJ 1922大陸争覇(最短)

タイトルリンク:http://61.187.179.132/JudgeOnline/problem.php?id=1922
标题:図に1~nを求める最短ルートがある.しかし、いくつかの点はいくつかの点が遍歴されてから歩くことができます.
考え方:制限がないのは普通の最短です.制限が多くなると、1つの配列記録が制限される点が増加し、制限要因によって最も早く時間を遍歴することができる.このように毎回2つの時間の最大値は、この点が遍歴できる最初の時間である.
 

int g[N][N],d1[N],d2[N],num[N];

bool a[N][N],visit[N];

int n,m;





void Dij()

{

    int i,j,k,Min;

    FOR1(i,n) d1[i]=INF;

    d1[1]=0;

    FOR1(i,n)

    {

        Min=INF; k=0;

        FOR1(j,n) if(!visit[j]&&!num[j]&&max(d1[j],d2[j])<Min)

        {

            Min=max(d1[j],d2[j]);

            k=j;

        }

        if(!k) break;

        visit[k]=1;

        FOR1(j,n) if(!visit[j])

        {

            if(a[k][j]) num[j]--,d2[j]=max(d2[j],Min);

            d1[j]=min(d1[j],Min+g[k][j]);

        }

    }

    PR(max(d1[n],d2[n]));

}





int main()

{

    RD(n,m); 

    int i,j,u,v,w;

    FOR1(i,n) FOR1(j,n) g[i][j]=INF;

    FOR1(i,m)

    {

        RD(u,v,w);

        if(g[u][v]>w) g[u][v]=w;

    }

    FOR1(i,n)

    {

        RD(num[i]);

        FOR1(j,num[i]) RD(u),a[u][i]=1;

    }

    Dij();

}