「bsoj1455」非法的摩的 - 分层图

题目大意

    在你的强力援助下，PCY成功完成了之前的所有任务，他觉得，现在正是出去浪的大好时光。
    于是，他来到高速公路上，找到一辆摩的前往几千公里以外他心仪的那家黄焖鸡米饭。
    由于 PCY的品味异于常人，途经几百个城市的黄焖鸡米饭他都不屑一顾，他只愿意前往他心中最好的那家，但是为了一碗二十块钱的黄焖鸡米饭，他不愿意花上几千块的路费，他希望路费尽量少。高速路上的警察叔叔被他的行为所打动，于是在多方协调下，最多$K$条城市之间的高速收费站愿意免费为PCY放行（可以任意选择）。
    显然，PCY已经筋疲力尽，不想再动用自己的数学天才来计算他可以花费的最小路费，因此他希望你可以帮他最后一次，他说他可以请你吃大碗的黄焖鸡米饭，还可以加一瓶豆奶。
    现在给你$N$个城市（编号为$0\ldots N-1$），$M$条道路，和每条高速公路的花费$W_i$ ，以及题目所描述的$K$。PCY想从城市$S$到城市$T$，因为他对$T$城市的黄焖鸡米饭情有独钟。

---

题目分析

分层图裸题，直接设二维状态进行Dijkstra。
似乎SPFA被卡。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=10005;
int n,m,s,t,k,dist[maxn][15],vst[maxn][15];
struct QueNode {
	int d,u,v;
	bool operator < (const QueNode& b) const {
		return d>b.d;
	}
};
struct Edge {
	int from,to,dist;
};
vector<Edge>edges[maxn];
void AddEdge(int x,int y,int v) {
	edges[x].push_back((Edge) {
		x,y,v
	});
}
void Dijkstra(int s) {
	for(int i=1; i<=n; i++)
		for(int j=0; j<=k; j++)
			dist[i][j]=0x7fffffff/2;
	dist[s][0]=0;
	priority_queue<QueNode>Q;
	Q.push((QueNode) {
		0,s,0
	});
	while(!Q.empty()) {
		QueNode Now=Q.top();
		Q.pop();
		if(vst[Now.u][Now.v])continue;
		vst[Now.u][Now.v]=1;
		for(Edge& e:edges[Now.u]) {
			int Next=e.to;
			if(dist[Next][Now.v]>dist[Now.u][Now.v]+e.dist) {
				dist[Next][Now.v]=dist[Now.u][Now.v]+e.dist;
				Q.push((QueNode) {
					dist[Next][Now.v],Next,Now.v
				});
			}
			if(Now.v<k&&dist[Next][Now.v+1]>dist[Now.u][Now.v]) {
				dist[Next][Now.v+1]=dist[Now.u][Now.v];
				Q.push((QueNode) {
					dist[Next][Now.v+1],Next,Now.v+1
				});
			}
		}
	}
}
int main() {
	n=Get_Int();
	m=Get_Int();
	k=Get_Int();
	s=Get_Int();
	t=Get_Int();
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		AddEdge(x,y,v);
		AddEdge(y,x,v);
	}
	Dijkstra(s);
	int ans=0x7fffffff/2;
	for(int i=0; i<=k; i++)ans=min(ans,dist[t][i]);
	printf("%d\n",ans);
	return 0;
}