【Heap-dijkstra】CDOJ1639 云中谁寄锦书来？雁字回时，月满西楼。

题意：在n个点m条边的无向图上，有k个出口从起点出发，每到一个点（包括起点），该点连出的边中有d条会被封锁求最坏情况下到达出口的最短路

题解：该题为dijkstra算法的拓展

由于求最坏情况下的最短路，对于每个点，显然最优的前d条边不能走

对于边u->v，必然要先得到v到出口的最坏情况下的最短路才能得到u经过该边再到出口的最坏情况下的最短路，也就是该边对于u的价值所以要从出口往回考虑

令f[i]表示i到出口的最坏情况下的最短路同dijkstra算法一样，每个点i可以分为f[i]已确定的和f[i]未确定的初始时自然是对于每个出口x，f[x]=0已确定

对于f[v]已确定的点v，将边权为w的边u->v以f[v]+w为关键字加入小根堆中

对于每个点i还要记录cnt[i]=k，表示到i后，i连出的最优的前k条边已被封锁

每次取出堆顶对应的边u->v（若f[u]已确定直接弹出）则该边为u连出的（除已被封锁的边外）最优的边若cnt[u]<d，该边必然会被封锁，那么将cnt[u]加1，弹出堆顶若cnt[u]=d，那么可以确定f[u]=f[v]+w，再用u更新连向u的边，弹出堆顶

重复这一过程直到确定f[0]的值，该值即为答案

不妨思考下为何不从起点开始考虑

若从起点开始考虑，令f[i]表示从起点到i的最坏情况下的最短路对于f[u]已确定的点u，将边权为w的边u->v以f[u]+w为关键字加入小根堆中每次取出堆顶对应的边u->v（若f[v]已确定直接弹出）若cnt[u]<d，该边必然会被封锁，那么将cnt[u]加1，弹出堆顶若cnt[u]=d，可以确定f[v]=f[u]+w，再用v更新v连向的边，弹出堆顶

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

struct Edge{

	int u,v,d;

};

bool operator < (const Edge &a,const Edge &b){

	return a.d>b.d;

}

priority_queue<Edge>Heap;

int n,m,K,d,f[100010],cnts[100010];

int v[2000010],__next[2000010],first[100010],w[2000010],e;

void AddEdge(int U,int V,int W){

	v[++e]=V;

	w[e]=W;

	__next[e]=first[U];

	first[U]=e;

}

int main(){

	int x,y,z;

	scanf("%d%d%d%d",&n,&m,&K,&d);

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

		scanf("%d%d%d",&x,&y,&z);

		AddEdge(x,y,z);

		AddEdge(y,x,z);

	}

	memset(f,0x7f,sizeof(f));

	for(int i=1;i<=K;++i){

		scanf("%d",&x);

		f[x]=0;

		cnts[x]=d+1;

		for(int j=first[x];j;j=__next[j]){

			Heap.push((Edge){v[j],x,w[j]});

		}

	}

	while(!Heap.empty()){

		Edge E=Heap.top(); Heap.pop();

		++cnts[E.u];

		if(cnts[E.u]==d+1){

			f[E.u]=E.d;

			for(int i=first[E.u];i;i=__next[i]){

				if(cnts[v[i]]<=d){

					Heap.push((Edge){v[i],E.u,f[E.u]+w[i]});

				}

			}

		}

	}

	printf("%d\n",f[0]>2000000000 ? -1 : f[0]);

	return 0;

}

巴特西

【Heap-dijkstra】CDOJ1639 云中谁寄锦书来？雁字回时，月满西楼。

最新文章

热门文章