BZOJ 1922[Sdoi2010]大陆争霸

作者: MayFlyyh 分类: 最短路 发布时间: 2018-05-25 12:47 ė 6 没有评论

BZOJ 1922[Sdoi2010]大陆争霸

Description

在一个遥远的世界里有两个国家:位于大陆西端的杰森国和位于大陆东端的 克里斯国。两个国家的人民分别信仰两个对立的神:杰森国信仰象征黑暗和毁灭 的神曾·布拉泽,而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。 幻想历 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。你只需摧毁位于杰森国首都 的曾·布拉泽大神殿,杰森国的信仰,军队还有一切就都会土崩瓦解,灰飞烟灭。 为了尽量减小己方的消耗,你决定使用自爆机器人完成这一任务。唯一的困 难是,杰森国的一部分城市有结界保护,不破坏掉结界就无法进入城市。而每个 城市的结界都是由分布在其他城市中的一些结界发生器维持的,如果想进入某个 城市,你就必须破坏掉维持这个城市结界的所有结界发生器。 现在你有无限多的自爆机器人,一旦进入了某个城市,自爆机器人可以瞬间 引爆,破坏一个目标(结界发生器,或是杰森国大神殿),当然机器人本身也会 一起被破坏。你需要知道:摧毁杰森国所需的最短时间。

Input

第一行两个正整数 N, M。 接下来 M行,每行三个正整数 ui, vi, wi,表示有一条从城市ui到城市 vi的单 向道路,自爆机器人通过这条道路需要 wi的时间。 之后 N 行,每行描述一个城市。首先是一个正整数 li,维持这个城市结界所 使用的结界发生器数目。之后li个1~N 之间的城市编号,表示每个结界发生器的 位置。如果 Li = 0,则说明该城市没有结界保护,保证L1 = 0 。

Output

仅包含一个正整数 ,击败杰森国所需的最短时间。

Sample Input
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
Sample Output
5
image

由于有无限多个机器人,所以不用逐个解除保护,也就转化成了最短路,也就是说时间不用叠加

带限制的最短路,要到达一个点必须先到达保护他的点

可以反过来,记录x点保护的点有哪些。

当点x已经可以到达,就释放他保护的点,如果他保护的点不再被保护,就加到队列中

然后实际到达x的时间为本来到达x的时间与保护x的所有点中最晚到达的

可以记dis[x]表示本来到达时间,d[x]表示保护x的所有点中最晚到达的

当已经可以进入x时,取dis[x]=std::max(dis[x],d[x])

一开始把小根堆写成了大根堆。。。。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#define iter std::vector<int>::iterator 
//错误原因 1 最短路 小根堆写成了大根堆
//         2 for循环内修改终止条件,导致后面的数字读入混乱 
const int N = 3100;
const int M = 73000; 
int n,m;
struct edge{
    int next,to,v;
}e[M*2];
struct heap{
    int name,v;
    bool operator < (const heap m) const {
        return v>m.v;
    }
};
int last[N],cnt;
int l[N],t[N],v[N],dis[N];
int cov[N];
std::vector<int> vec[N]; 
inline int add(int x,int y,int z){
    cnt++;
    e[cnt].next=last[x],last[x]=cnt;
    e[cnt].v=z,e[cnt].to=y;
}
inline int check(int x){
    printf("%d %d %d %d\n",x,dis[x],t[x],l[x]);
    int xx;
    scanf("%d",&xx);
    return 0;
}
inline void Dijkstra(){
    std::priority_queue<heap> q;
    while(!q.empty()) q.pop();
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;q.push((heap){1,0});
    while(!q.empty()){
        heap tmp = q.top();q.pop();
        int x = tmp.name;
        if(v[x]) continue;
        if(l[x]) continue;
        v[x]=1;
        dis[x]=std::max(dis[x],t[x]);
        for(iter it=vec[x].begin();it!=vec[x].end();++it){
            l[*it]--;
            t[*it]=std::max(t[*it],dis[x]);
            if(!l[*it] ) q.push((heap){*it,dis[*it]});
        }
        for(int i=last[x];i;i=e[i].next){
            if(dis[x]+e[i].v<dis[e[i].to]){
                dis[e[i].to]=dis[x]+e[i].v;
                q.push((heap){e[i].to,dis[e[i].to]});
            }
        }
    }
}
int main (){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&l[i]);
        int x,derta=0;
        for(int j=1;j<=l[i];++j){
            scanf("%d",&x);
            vec[x].push_back(i);
        }
    }
    Dijkstra();
    printf("%d",std::max(t[n],dis[n]));
    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/209

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部