POJ 1724 分层图最短路

分层图的两种建法

1：直接建k-1层图

2：给dis或vis或你需要记录信息的数组额外增加一维模拟n层图的效果

至于分层图的理解，个人认为就是有一些干扰信息时，比如免费经过一些路径或者有特殊限制的时候，可以从当前图免费跳到下一层或上一层图来转换状态。

#include <cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int maxn = 1e3+10, maxm = 1e5+10;
int k,n,m;
int tot,head[maxn],dis[101][10001],vis[101][10001];
struct Edge
{
	int to,nxt,len,cos;
}e[maxm];
struct Node{
	int to,k,len;
	bool operator <(const Node&b)const
	{
		return len > b.len;
	}
	Node(int to,int k,int len):to(to),k(k),len(len){}
};
void add(int from,int to,int l,int c)
{
	e[tot].to = to, e[tot].len = l; e[tot].cos = c, e[tot].nxt = head[from];
	head[from] = tot++;
}
void dij()
{
	for(int i=1;i<=n; ++i)
	for(int j=0;j<=k;++j) dis[i][j]=0x7f7f7f7f;
	priority_queue<Node> q;
	q.push(Node(1,k,0));
	dis[1][k] = 0;
 	while(!q.empty())
	{
		Node u = q.top(); q.pop();
		if(vis[u.to][u.k]) continue;
		vis[u.to][u.k] = 1;
		for(int i = head[u.to]; ~i; i = e[i].nxt)
		{
			int v = e[i].to;
			if( u.k >= e[i].cos)
			{
				if(dis[v][u.k-e[i].cos] > dis[u.to][u.k]+e[i].len)
				{
					dis[v][u.k-e[i].cos] = dis[u.to][u.k] + e[i].len;
					q.push(Node(v,u.k-e[i].cos,dis[v][u.k-e[i].cos]));
				}
			}
		}
	}
}
int main()
{
	memset(head,-1,sizeof(head)); tot = 0;
	scanf("%d%d%d",&k,&n,&m);
	for(int i = 0,u,v,l,c; i < m; ++i)
	{
		scanf("%d%d%d%d",&u,&v,&l,&c);
		add(u,v,l,c);	
	}	
	dij();
	int ans = 0x7f7f7f7f;
	for(int i = 0; i <= k; ++i)  ans = min(ans,dis[n][i]);
	if(ans == 0x7f7f7f7f) ans = -1;
	printf("%d\n",ans); 
	return 0;
}