BZOJ 1922 [Sdoi2010] 大陆争霸

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1922

题意：n 个点的有向图，到一个点的前提是保护它的点都去过了，点之间有保护的关系，同时可以派出任意多的人，求 1-n 最短路...

有人说这是分层图最短路... 那就是吧...

记录\({d1}_i\) 为到 i 点的路程时间，\({d2}_i\) 为保护 i 点的点全去过的时间，那么 i 点的真实进入时间为\(max({d1}_i,{d2}_i)\)

跑最短路时按照真实时间更新即可，需要注意的是，一个点可以入队当且仅当保护它的点全去过了

数组的含义在注释里给出了

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 3010
#define M 70010
#define ll long long
using namespace std;
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
typedef pair<int,int> r;
struct zgz
{
	int next,to,val;
}edge[M];
int cnt=1,head[M];
void add(int from,int to,int val)
{
	edge[cnt].to=to;
	edge[cnt].val=val;
	edge[cnt].next=head[from];
	head[from]=cnt++;
}
int cnt_udpt[N],cnt_pt[N],prot[N][N];//prot protect 第i个城市的第j个保护城市是什么 
//cnt_udpt cnt_underprotect 第i个城市被多少个城市保护 cnt_pt cnt_protect 第i个城市保护几个城市 
int n,m,u,v,w,tmp,S;
int d1[N],d2[N];
bool vis[N];
priority_queue<r,vector<r>,greater<r> >q;
void dijkstra()//d1 什么时候到i城 d2什么时候i城失去保护
{
	memset(d1,0x3f,sizeof(d1));
	d1[S]=0;q.push(make_pair(0,S));
	while(!q.empty())
	{
		int x=q.top().second;q.pop();
		if(vis[x])continue;vis[x]=1;
		int mx=max(d1[x],d2[x]);
		for(int i=head[x];i;i=edge[i].next)
		{
			int to=edge[i].to,val=edge[i].val;
			if(d1[to]>mx+val)
			{
				d1[to]=mx+val;
				if(!cnt_udpt[to])q.push(make_pair(max(d1[to],d2[to]),to));
			}
		}
		for(int i=1;i<=cnt_pt[x];i++)
		{
			int to=prot[x][i];
			cnt_udpt[to]--;d2[to]=max(d2[to],mx);
			if(!cnt_udpt[to])q.push(make_pair(max(d1[to],d2[to]),to));
		}
	}
}
int main()
{
	n=read(),m=read();S=1;
	for(int i=1;i<=m;i++)
	{
		u=read(),v=read(),w=read();
		add(u,v,w);
	}
	for(int i=1;i<=n;i++)
	{
		cnt_udpt[i]=read();
		for(int j=1;j<=cnt_udpt[i];j++)
		{
			tmp=read();
			prot[tmp][++cnt_pt[tmp]]=i;
		}
	}
	dijkstra();
	printf("%d",max(d1[n],d2[n]));
}

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 3010

#define M 70010

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

typedef pair<int,int> r;

struct zgz

{

int next,to,val;

}edge[M];

int cnt=1,head[M];

void add(int from,int to,int val)

{

edge[cnt].to=to;

edge[cnt].val=val;

edge[cnt].next=head[from];

head[from]=cnt++;

}

int cnt_udpt[N],cnt_pt[N],prot[N][N];//prot protect 第i个城市的第j个保护城市是什么

//cnt_udpt cnt_underprotect 第i个城市被多少个城市保护 cnt_pt cnt_protect 第i个城市保护几个城市

int n,m,u,v,w,tmp,S;

int d1[N],d2[N];

bool vis[N];

priority_queue<r,vector<r>,greater<r> >q;

void dijkstra()//d1 什么时候到i城 d2什么时候i城失去保护

{

memset(d1,0x3f,sizeof(d1));

d1[S]=0;q.push(make_pair(0,S));

while(!q.empty())

{

int x=q.top().second;q.pop();

if(vis[x])continue;vis[x]=1;

int mx=max(d1[x],d2[x]);

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(d1[to]>mx+val)

{

d1[to]=mx+val;

if(!cnt_udpt[to])q.push(make_pair(max(d1[to],d2[to]),to));

}

for(int i=1;i<=cnt_pt[x];i++)

{

int to=prot[x][i];

cnt_udpt[to]--;d2[to]=max(d2[to],mx);

if(!cnt_udpt[to])q.push(make_pair(max(d1[to],d2[to]),to));

}

int main()

{

n=read(),m=read();S=1;

for(int i=1;i<=m;i++)

{

u=read(),v=read(),w=read();

add(u,v,w);

}

for(int i=1;i<=n;i++)

{

cnt_udpt[i]=read();

for(int j=1;j<=cnt_udpt[i];j++)

{

tmp=read();

prot[tmp][++cnt_pt[tmp]]=i;

}

dijkstra();

printf("%d",max(d1[n],d2[n]));

}

zgz233

zgz233

BZOJ 1922 [Sdoi2010] 大陆争霸

l1ll5

Comments | NOTHING