[BJWC2012]冻结

luogu

BZOJ

分层图最短路,层与层之间连半边权边

#include<bits/stdc++.h>

using namespace std;

const int _=5000;

int re(){

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

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

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

	return x*w;

}

int n,m,k,cnt,ans=1e9;

int h[_],d[_];

bool vis[_];

struct node{int id,d;};

struct edge{int to,next,w;}e[400000];

bool operator <(node a,node b){return a.d>b.d;}

priority_queue<node>q;

void link(int u,int v,int w){

	e[++cnt]=(edge){v,h[u],w};h[u]=cnt;

}

void dij(){

	memset(d,63,sizeof(d));

	d[1]=0;q.push((node){1,0});

	while(!q.empty()){

		int u=q.top().id;q.pop();vis[u]=1;

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

			int v=e[i].to;

			if(d[v]>d[u]+e[i].w){

				d[v]=d[u]+e[i].w;

				if(!vis[v])q.push((node){v,d[v]});

			}

		}

	}

}

int main(){

	n=re(),m=re(),k=re();

	while(m--){

		int a=re(),b=re(),c=re();

		link(a,b,c);link(b,a,c);

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

			link(i*n+a,i*n+b,c);

			link(i*n+b,i*n+a,c);

			link((i-1)*n+a,i*n+b,c>>1);

			link((i-1)*n+b,i*n+a,c>>1);

		}

	}

	dij();

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

		ans=min(ans,d[i*n]);

	printf("%d\n",ans);

	return 0;

}

巴特西

[BJWC2012]冻结

[BJWC2012]冻结

最新文章

热门文章