洛谷 P2446 [SDOI2010]大陆争霸 题解【优先队列bfs】【最短路】【贪心】

点击量：169

    本来思路对了但是转移写麻烦了把自己绕进去了。

目录

题目背景

在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。

幻想历8012年1月，杰森国正式宣布曾·布拉泽是他们唯一信仰的神，同时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。

幻想历8012年3月2日，位于杰森国东部小镇神谕镇的克里斯国教徒发动起义。

幻想历8012年3月7日，神谕镇的起义被杰森国大军以残酷手段镇压。

幻想历8012年3月8日，克里斯国对杰森国宣战。由数十万大军组成的克里斯军团开至两国边境，与杰森军团对峙。

幻想历8012年4月，克里斯军团攻破杰森军团防线进入神谕镇，该镇幸存的克里斯国教徒得到解放。

战争随后进入胶着状态，旷日持久。战况惨烈，一时间枪林弹雨，硝烟弥漫，民不聊生。

题目描述

幻想历8012年5月12日深夜，斯普林·布拉泽降下神谕：“Trust me, earn eternal life.”克里斯军团士气大增。作为克里斯军团的主帅，你决定利用这一机会发动奇袭，一举击败杰森国。具体地说，杰森国有N个城市，由M条单向道路连接。神谕镇是城市1而杰森国的首都是城市N。你只需摧毁位于杰森国首都的曾·布拉泽大神殿，杰森国的信仰，军队还有一切就都会土崩瓦解，灰飞烟灭。

为了尽量减小己方的消耗，你决定使用自爆机器人完成这一任务。唯一的困难是，杰森国的一部分城市有结界保护，不破坏掉结界就无法进入城市。而每个城市的结界都是由分布在其他城市中的一些结界发生器维持的，如果想进入某个城市，你就必须破坏掉维持这个城市结界的所有结界发生器。

现在你有无限多的自爆机器人，一旦进入了某个城市，自爆机器人可以瞬间引爆，破坏一个目标（结界发生器，或是杰森国大神殿），当然机器人本身也会一起被破坏。你需要知道：摧毁杰森国所需的最短时间。

输入输出格式

输入格式：

输入文件的landcraft.in的第一行两个正整数N, M。

接下来M行，每行三个正整数ui, vi, wi，表示有一条从城市ui到城市vi的单向道路，自爆机器人通过这条道路需要wi的时间。

之后N行，每行描述一个城市。首先是一个正整数li，维持这个城市结界所使用的结界发生器数目。之后li个1~N之间的城市编号，表示每个结界发生器的位置。如果li = 0，则说明该城市没有结界保护，保证l1 = 0 。

输出格式：

输出文件landcraft.out仅包含一个正整数 ，击败杰森国所需的最短时间。

输入输出样例

输入样例#1： 复制

6 6
1 2 1
1 4 3
2 3 1
2 5 2
4 6 2
5 3 2
0
0
0
1 3
0
2 3 5

输出样例#1：

5

题解：

    类似拓扑排序，要等所有结界处理完了才能进行操作。因此一个点最早能被到达的时间是它的结界被完全破坏的时间与它被入边更新的最早时间中的最大值。

    图上灰色边表示保护边。

    左图中尽管在时刻5时5号节点的结界就解除了，但是他自己的入边还没有被激活，因此答案是9。

    右图中在时刻4时5号节点就有入边被激活，但是它还有结界防御，因此答案是5。

    因为我们要找最早时间，而一个点要同时满足两个条件才能被访问，要有已经激活的入边，且所有结界点被访问过。所有结界点被访问过就像拓扑排序一样，访问一个就把in–。而有激活的入边且满足最短，就联想到Dijkstra的松弛操作。

    也就是说，通过松弛操作，最优入边一定在 从某个点第一次被更新 到访问到这个点 之间出现。因为Dijkstra有堆优化，每次从代价最小的出去更新，当更新到某点时，已经没有比它更近的，更确切地说，是没有能引入它的更近的点了。

    因此每次解除结界时，查询目标节点是否完全解除并有入边，更新结界最早访问时间与目标节点最早访问时间中的较大值。同理在松弛时，也这样查询一遍。

    最终只用一个f数组就能存下所有状态。并且类似拓扑排序的结构具有阶段性，保证了正确性。

Code：

#include<cstdio>
#include<cstring>
#include<queue>
using std::priority_queue;
int min(int x,int y)
{
    return x<y?x:y;
}
int max(int x,int y)
{
    return x>y?x:y;
}
struct statu
{
    int dis,n;
    statu(int n,int dis)
    {
        this->n=n;
        this->dis=dis;
    }
    friend bool operator <(statu a,statu b)
    {
        return a.dis>b.dis;
    }
};
struct edge
{
    int n,v;
    int nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[141000],pro[141000];
int head[3100],ecnt=-1,hpro[3100],pcnt=-1;
void add(int from,int to,int v)//单向边
{
    e[++ecnt]=edge(to,v,head[from]);
    head[from]=ecnt;
}
void addp(int from,int to)
{
    pro[++pcnt]=edge(to,1,hpro[from]);
    hpro[from]=pcnt;
}
int open[3100],in[3100];
int f[3100];
priority_queue<statu> q;
void bfs()
{
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    q.push(statu(1,0));
    while(!q.empty())
    {
        statu k=q.top();
        q.pop();
        if(f[k.n]<k.dis)
            continue;
        for(int i=head[k.n];~i;i=e[i].nxt)
        {
            open[e[i].n]=1;
            if(f[k.n]+e[i].v<f[e[i].n])
            {
                f[e[i].n]=f[k.n]+e[i].v;
                if(in[e[i].n]==0)
                    q.push(statu(e[i].n,f[e[i].n]));
            }
        }
        for(int i=hpro[k.n];~i;i=pro[i].nxt)//都更新一遍
        {
            f[pro[i].n]=max(f[pro[i].n],f[k.n]);
            in[pro[i].n]--;
            if(in[pro[i].n]==0&&open[pro[i].n])//是否可以引入
                q.push(statu(pro[i].n,f[pro[i].n]));
        }
    }
}
int main()
{
    memset(open,0,sizeof(open));
    open[1]=1;
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    memset(hpro,-1,sizeof(hpro));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&in[i]);
        for(int j=1;j<=in[i];j++)
        {
            scanf("%d",&u);
            addp(u,i);
        }
    }
    bfs();
    printf("%d\n",f[n]);
    return 0;
}