关键词：
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
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; int n,m; const int N=3e3+7; int d1[N],d2[N],way[N][N]; bool p[N][N]; int num[N]; bool vis[N]; int inf; inline void dij() memset(d1,127/3,sizeof(d1)); d1[1]=0; fo(i,1,n) int now,mn=inf; fo(j,1,n) if (!num[j]&&!vis[j]&&max(d1[j],d2[j])<mn) now=j; mn=max(d1[j],d2[j]); if (!now)break; vis[now]=1; fo(j,1,n) if (!vis[j]) if (p[now][j])num[j]--,d2[j]=max(d2[j],mn); if (way[now][j]) d1[j]=min(d1[j],mn+way[now][j]); printf("%d ",max(d1[n],d2[n])); int main() scanf("%d%d",&n,&m); memset(way,127/3,sizeof(way)); inf=way[1][1]; fo(i,1,m) int x,y,z; scanf("%d%d%d",&x,&y,&z); way[x][y]=min(way[x][y],z); fo(i,1,n) scanf("%d",&num[i]); fo(j,1,num[i]) int x; scanf("%d",&x); p[x][i]=1; dij(); return 0;
//d1[i]表示到达i点的最短时间，d2[i]表示能够破坏i点的最短时间。 #include<cstdio> #include<iostream> #include<cstring> #include<queue> #define N 3010 #define M 70010 using namespace std; int head[N],d[N],d1[N],d2[N],vis[N],grap[N][N],n,m; struct nodeint v,w,pre;e[M]; struct Node int x,dist; bool operator<(Node s1) const return dist>s1.dist; ;priority_queue<Node> q; void add(int i,int u,int v,int w) e[i].v=v;e[i].w=w;e[i].pre=head[u];head[u]=i; void Dij() memset(d1,127/3,sizeof(d1)); q.push((Node)1,0);d1[1]=0; while(!q.empty()) int u=q.top().x,mx=q.top().dist;q.pop(); if(vis[u]) continue;vis[u]=1; for(int i=head[u];i;i=e[i].pre) int v=e[i].v; if(d1[v]>mx+e[i].w) d1[v]=mx+e[i].w; if(!d[v]) q.push((Node)v,max(d1[v],d2[v])); for(int i=1;i<=grap[u][0];i++) int v=grap[u][i];d[v]--; d2[v]=max(d2[v],mx); if(!d[v]) q.push((Node)v,max(d1[v],d2[v])); printf("%d",max(d1[n],d2[n])); int main() scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) int u,v,w;scanf("%d%d%d",&u,&v,&w); add(i,u,v,w); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int j=1;j<=d[i];j++) int x;scanf("%d",&x); grap[x][++grap[x][0]]=i; Dij(); return 0;
bzoj1922[sdoi2010]大陆争霸堆优化dijkstra
题目描述一张n个点m条边的图，通过每条边需要一定的时间。有一些限制条件，每个限制条件形如“x保护y”，表示到达y的最短时间不能小于到达x的最短时间（即如果在其之前到达，则需要等待至xd到达）。问1到n的最短时... 查看详情
bzoj1922:[sdoi2010]大陆争霸
题面传送门Sol走到一个点的前提是所有的影响它的点都走到，并且它的时间为那些点的时间\(max\)与自己的最短路的\(max\)考虑\(Dijkstra\)每次松弛时候，把它影响到的点的防护罩减\(1\)如果某个点没有后继影响它的节点就丢到大根... 查看详情
bzoj1922[sdoi2010]大陆争霸最短路
题目在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉... 查看详情
bzoj1922sdoi2010大陆争霸最短路
题意：给定一个图，图中有保护关系(u,v)表示到v之前必须先到一次u，求从1到N的最短路题解：定义d1[i]为直接到达i的最短距离，这个的更新和普通的Dijkstra一样定义d2[i]为解除i的所有保护的最短距离（不一定要在i结束），这个更... 查看详情
bzoj1922[sdoi2010]大陆争霸dijkstra
Description具体地说，杰森国有N个城市，由M条单向道路连接。神谕镇是城市1而杰森国的首都是城市N。你只需摧毁位于杰森国首都的曾·布拉泽大神殿，杰森国的信仰，军队还有一切就都会土崩瓦解，灰飞烟灭。为了尽量减小... 查看详情
bzoj1922--大陆争霸(最短路)
看起来很难的最短路。。。。题目链接： http://www.lydsy.com/JudgeOnline/problem.php?id=1922 Solution 如果要要进入某个城市，首先要进入几个特定的点。。。 于是进入某个城市的时间就是到达该城市和... 查看详情
bzoj1922大陆争霸
有点迷，spfa好像不好写，必须dijkstra#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#definemaxv3050#definemaxe70050usingnamespacestd;intn,m,x,y,z 查看详情
ac日记——[sdoi2010]大陆争霸洛谷p3690
[SDOI2010]大陆争霸 思路： dijkstra模板； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn3005#definelllonglong#definemaxm70002<<2#defineINF1e13structNodeType{llid,dis;booloperator 查看详情
[sdoi2010]大陆争霸(代码片段)
嘟嘟嘟 首先可以知道，对于在哪个时候攻占一个城市，应该是他的最短到达时间和最早进入时间的最大值（max(d1[i],d2[i])）。最短到达时间：就是朴素的最短路d1[i]。最早进入时间：设所有到达有他的结界发生器的城市为j，... 查看详情
dijkstrap2446[sdoi2010]大陆争霸(代码片段)
Background在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布... 查看详情
p2446[sdoi2010]大陆争霸(代码片段)
P2446[SDOI2010]大陆争霸题意：n个点，m个边，wi为每个边的边权，对于每个点i，其被l个点保护着，也就是如果保护其的点没有被破坏，点i无法被破坏(也无法经过其前往其他点)。现在从1出兵(无限数量)... 查看详情
p2446[sdoi2010]大陆争霸(有限制的最短刘）(代码片段)
题目描述幻想历8012年5月12日深夜，斯普林·布拉泽降下神谕：“Trustme,earneternallife.”克里斯军团士气大增。作为克里斯军团的主帅，你决定利用这一机会发动奇袭，一举击败杰森国。具体地说，杰森国有N个城市，... 查看详情
bzoj1975:[sdoi2010]魔法猪学院
二次联通门: BZOJ1975:[Sdoi2010]魔法猪学院 /*BZOJ1975:[Sdoi2010]魔法猪学院k短路统计一下在能量用完之前走了多少条到终点的路即可*/#include<cstdio>#include<queue>#include<iostream>#include<cstring 查看详情
bzoj1941sdoi2010hideansseek
1941:[Sdoi2010]HideandSeekTimeLimit: 16Sec MemoryLimit: 162MBSubmit: 1544 Solved: 829[Submit][Status][Discuss]Description小猪iPig在PKU刚上完了无聊的猪性代数课，天资聪慧的iPig被这门对他 查看详情
bzoj1926:[sdoi2010]粟粟的书架
1926:[Sdoi2010]粟粟的书架TimeLimit:30Sec MemoryLimit:552MBSubmit:1013 Solved:396[Submit][Status][Discuss]Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟... 查看详情
bzoj1924sdoi2010所驼门的宝藏
1924:[Sdoi2010]所驼门王的宝藏TimeLimit: 5Sec MemoryLimit: 128MBSubmit: 1380 Solved: 603[Submit][Status][Discuss]DescriptionInput第一行给出三个正整数N,R,C。以下N行，每行给出一扇传送门的信息，包含三 查看详情
bzoj1975[sdoi2010]魔法猪学院
1975:[Sdoi2010]魔法猪学院TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 1758 Solved: 557[Submit][Status][Discuss]DescriptioniPig在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和 查看详情
bzoj1951sdoi2010古代猪文
1951:[Sdoi2010]古代猪文TimeLimit: 1Sec MemoryLimit: 64MBSubmit: 3330 Solved: 1448[Submit][Status][Discuss]Description“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿 查看详情