【BZOJ1922】大陆争霸（最短路）

题面

BZOJ

洛谷

题解

最短路变形题。

定义\(dis\)表示最短路，\(d\)表示最早可以进入当前点的时间。显然\(d=max(max(dis_v,d_v))\)，其中\(v\)有着当前点的结节发生器。

那么Dijkstra跑一遍就好了。

注意一下这题边是单向的。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define MAX 3030

#define MAXL 70070

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

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

	return t?-x:x;

}

struct Line{int v,next,w;}e[MAXL<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

struct Node{ll dis;int u;};

bool operator<(Node a,Node b){return a.dis>b.dis;}

priority_queue<Node> Q;

int n,m;

ll dis[MAX],d[MAX];int dg[MAX];

vector<int> E[MAX];

bool vis[MAX];

void Dijkstra()

{

	Q.push((Node){dis[1]=0,1});

	while(!Q.empty())

	{

		Node x=Q.top();Q.pop();

		int u=x.u;ll dd=max(dis[u],d[u]);

		if(vis[u])continue;vis[u]=true;

		for(int i=h[u];i;i=e[i].next)

		{

			int v=e[i].v;if(vis[v])continue;

			if(dis[v]>dd+e[i].w)

			{

				dis[v]=dd+e[i].w;

				if(!dg[v])Q.push((Node){max(d[v],dis[v]),v});

			}

		}

		for(int i=0,l=E[u].size();i<l;++i)

		{

			int v=E[u][i];--dg[v];

			d[v]=max(d[v],dd);

			if(!dg[v])Q.push((Node){max(d[v],dis[v]),v});

		}

	}

}

int main()

{

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

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

	{

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

		Add(u,v,w);

	}

	memset(dis,63,sizeof(dis));

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

	{

		int k=read();dg[i]=k;

		while(k--)E[read()].push_back(i);

	}

	Dijkstra();

	printf("%lld\n",max(d[n],dis[n]));

	return 0;

}