题目链接：bzoj1922-大陆争霸

题意：给定n个点，m条边，从1点出发，给出一些限制，到达某些点时需要先到达一些特定的点（即一个点可能被其他点保护），求到达n点的最快时间

题解：

带限制的最短路问题。

d[i]记录i点被多少个点保护，dis1[i]表示到i点的到达时间，dis2[i]表示到i点的可进入时间，到达i点的真实时间即为max(dis1[i],dis2[i])。

每次从堆中取出一个真实时间最小的点，更新这个点连接的点d1，和这个点保护的点d2，然后d[i]--,若d[i]==0,那么i点就可以入堆

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
int n,m;
int d[3009],a[3009][3009],l[3009];
int edge[3009][3009];
struct node
{
    int u;
    int d;
    node(int u,ll d):u(u),d(d){}
    bool operator < (const node &a) const
    {
        return d>a.d;
    }
};
bool used[3009];
int dis1[3009];
int dis2[3009];
void dijkstra()
{
    priority_queue<node>    que;
    while(!que.empty()) que.pop();
    for(int i=1;    i<=n;   i++)
        dis1[i]=inf;
    dis1[1]=0;
    que.push(node(1,dis1[1]));
    memset(used,0,sizeof(used));
    while(!que.empty())
    {
        int u=que.top().u;
        que.pop();
        if(used[u]) continue;
        int maxV=max(dis1[u],dis2[u]);
        used[u]=1;
        for(int i=1;    i<=n;   i++)
        {
            if(edge[u][i]==inf) continue;
            if(used[i]) continue;
            if(dis1[i]>maxV+edge[u][i])
            {
                dis1[i]=maxV+edge[u][i];
                if(!d[i])   que.push(node(i,max(dis1[i],dis2[i])));
            }
        }
        for(int i=1;    i<=l[u];    i++)
        {
            int t=a[u][i];
            d[t]--;
            dis2[t]=max(dis2[t],maxV);
            if(!d[t])   que.push(node(t,max(dis1[t],dis2[t])));
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;    i<=n;   i++)
        for(int j=1;    j<=n;   j++)
            edge[i][j]=inf;
    for(int i=1;    i<=n;   i++)
        edge[i][i]=0;
    for(int i=1;    i<=m;   i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        edge[u][v]=min(edge[u][v],w);
    }
    for(int i=1;    i<=n;   i++)
    {
        scanf("%d",&d[i]);
        //d[i]表示保护i点的点数
        for(int j=1;    j<=d[i];    j++)
        {
            int u;
            scanf("%d",&u);
            a[u][++l[u]]=i;
            //l[i]表示i点保护的点数
        }
    }
    dijkstra();
    printf("%d\n",max(dis1[n],dis2[n]));
    return 0;
}