BZOJ-1922: [Sdoi2010]大陆争霸

[文章目录]

Description

给你n个点m条边的有向图,通过每条边都需要花费时间。现在你想用最短的时间从1号点到达n号点。每个点想到达它是有条件的,每个点都有一些前继节点(可能没有),该节点在某时间可达当且仅当其前继节点在该时间已经被达到。你可以派出任意多的士兵从一号点出发去往任意节点,询问到达n号点的最短时间,数据保证一定有解。N<=3,000,M<=70,000,1<=wi<=10^8

带有条件限制的最短路。一般的套路就是根据题目来改变最短路的算法。
假设一个节点有前继节点s个,那么这个节点的最短路程=max(原图中通过已经到达的节点到达其的最短路程,到达其s个前继节点的最长时间)。我们维护一个堆维护已经到达节点时间中的最短的,来更新其他节点。
将以其为前继节点的点的出度-1,如果为0,说明当前节点是最后到达的前继节点,如果已经达到原图的点,将路程取max扔入堆中,反之,则不扔。
在原图中更新其连向的点的时间,如果连向的点已经没有前继节点未达到,将其扔到堆中。保证只会被前继或是原图节点中的一个更新扔到堆中。
感性理解一下,好像是个dij?

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 3100
#define M 70100
const int inf=0x3f3f3f3f;
int n,m;
int head[N],to[M],nxt[M],date[M],cnt;
inline void add(int x,int y,int z)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    date[cnt]=z;
    head[x]=cnt;
}
int l[N];
vector<int> ve[N];
int dis[N];
struct node
{
    int x,dis;
};
bool operator < (node x,node y){return x.dis>y.dis;}
priority_queue <node> q;
inline void dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0; q.push((node){1,0}); int x,y;
    while(!q.empty())
    {
        x=q.top().x; y=q.top().dis; q.pop();
        if(y>dis[x]) continue;
        for(int i=head[x];i;i=nxt[i]) if(y+date[i]<dis[to[i]])
        {
            dis[to[i]]=y+date[i];
            if(!l[to[i]]) q.push((node){to[i],dis[to[i]]});
        }
        for(int i=0;i<(int)ve[x].size();++i)
        {
            l[ve[x][i]]--;
            if(!l[ve[x][i]]&&dis[ve[x][i]]!=inf)
            {
                dis[ve[x][i]]=max(dis[ve[x][i]],y);
                q.push((node){ve[x][i],dis[ve[x][i]]});
            }
        }
    }
    printf("%d",dis[n]);
}
int main()
{
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    for(int i=1;i<=n;++i)
    {
        scanf("%d",l+i);
        for(int j=1;j<=l[i];++j)
        {
            scanf("%d",&x);
            ve[x].push_back(i);
        }
    }
    dijkstra();
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注