bzoj1922: [Sdoi2010]大陆争霸分层图最短路-CSDN博客

本文链接：https://blog.csdn.net/EOD_realize/article/details/36874841

最短路问题，d2表示把这个城市所有的保护网破坏的最晚时刻，d1代表到达这个城市的时刻。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int save[3100][3100],d1[3100],d2[3100],num[3100];
bool p[3100][3100],vis[3100];
int m,n;
void dij()
{
    for(int i=1;i<=n;i++)
    {
        d1[i]=0x3f3f3f3f;
    }
    d1[1]=0;

    int flag,minn;
    for(int i=1;i<=n;i++)
    {
        minn=0x3f3f3f3f,flag=0;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&max(d1[j],d2[j])<minn&&!num[j])
            {
                minn=max(d1[j],d2[j]);
                flag=j;
            }
        }
        if(flag)
        {
            vis[flag]=1;
        }
        else
        {
            break;
        }
        for(int j=1;j<=n;j++) if(!vis[j])
        {
            if(p[flag][j]) num[j]--,d2[j]=max(d2[j],minn);
            d1[j]=min(d1[j],minn+save[flag][j]);
        }
    }
    printf("%d",max(d1[n],d2[n]));
}
int main()
{
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            save[i][j]=0x3f3f3f3f;
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        save[x][y]=min(save[x][y],z);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        for(int j=1;j<=num[i];j++)
        {
            scanf("%d",&y);
            p[y][i]=1;
        }
    }
    dij();
    return 0;
}