[BJWC2012]冻结 分层图最短路

昨晚飞行路线之后，这道题就应该能一眼切了

题目当然也不难，跑一遍分层图最短路即可

Code:

#include<cstring>

#include<algorithm>

#include<queue>

#include<string>

#include<cstdio>

using namespace std;

void setIO(string a){

	freopen((a+".in").c_str(),"r",stdin);

}

const int maxn=300000+4;

const double inf=2000000000;

int n,m,s,cnt,k,t;

int head[maxn],to[maxn],nex[maxn];

double val[maxn];

void addedge(int u,int v,double c){

	nex[++cnt]=head[u], head[u]=cnt, to[cnt] = v, val[cnt] = c;

}

struct Node{

	int u;

	double dist;

	Node(int u=0,double dist = 0.0):u(u),dist(dist){}

	bool const operator<(Node v) const {

		return v.dist<dist;

	}

};

priority_queue<Node>Q;

double d[maxn];

bool done[maxn];

void dijkstra(){

	memset(done,false,sizeof(done));

	for(int i=0;i<maxn;++i) d[i]=inf;

	Q.push(Node(s,0.0)); d[s]=0.0;

    while(!Q.empty()){

    	int u=Q.top().u; Q.pop();

    	if(done[u]) continue;

    	done[u]=true;

    	for(int v=head[u];v;v=nex[v]){

    		if(d[u]+val[v]<d[to[v]]){

    			d[to[v]]=d[u]+val[v];

    			Q.push(Node(to[v],d[to[v]]));

    		}

    	}

    }

}

int main(){

	//setIO("input");

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

	s=1, t=maxn - 3;

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

		int a,b,c;

		scanf("%d%d%d",&a,&b,&c);

		for(int j=0;j<=k;++j){

			addedge(a,b,(double)c);

			addedge(b,a,(double)c);

			if(j<k) addedge(a,b+n,(double)c/2);

			if(j<k) addedge(b,a+n,(double)c/2);

			a+=n, b+=n;

		}

	}

	for(int i=0;i<=k;++i) addedge(n+i*n,t,0);

	dijkstra();

    printf("%d",(int)d[t]);

    return 0;

}