2019.10.29 CSP%您赛第四场t2 迷路（star）

我太菜了我竟然不会分层图最短路

【题目描述】
(cxm) 在 (ns) 星系迷路了，情急之下，他找到了你。现在，解救 (cxm) 的重任就落在了
你的肩上了。
(ns) 星系有 (n) 颗星球，编号为 (1) 到 (n) 的整数。星球之间由 (m) 条单向的时空隧道相
连。经过每个时空隧道要花费一定的时间。(cxm) 的飞船最多可以存储 (max)(\_)(energy) 的能
量，经过有些时空隧道会损失能量，而其他的会增加能量。飞船不能通过损失能量数超
过当前能量或者增加能量后飞船能量超过 (max\_energy) 的时空隧道。
现在，(cxm) 的飞船在编号为 (1) 的星球，飞船剩余的能量为 (max\_energy) 的一半。你
需要计算出到编号为 (n) 的星球的最短时间。
【输入格式】
从文件 (star.in) 中读入数据。
第一行三个正整数 (n,m) 和 (max\_energy)。
接下来 (m) 行，每行 (3) 个正整数 (u,v,time) 和 (1) 个整数 (energy)。表示从编号为 (u) 的星
球到编号为 (v) 的星球有一条时空隧道，经过这个隧道花费的时间为 (time)。如果 (energy)
为正数，则表示通过会增加 (energy) 的能量，否则表示通过会损失 (−energy) 的能量。保
证，(1leq u,vleq n，1leq timeleq 10^4 ，−100leq energyleq 100)。
每行两个数之间均用空格隔开。
【输出格式】
输出到文件 (star.out) 中。
输出一行，一个正整数，表示到达的最短时间。数据保证有解。
【样例输入】
4 6 4
1 4 100 0
1 2 5 -1
2 3 3 2
3 2 1 -1
3 4 5 -4
3 4 10 -3

【样例输出】
17
【子任务】
每个测试点的数据规模如下

容易想到最短路。但是因为有(energy)限制的存在，所以不能跑简单的最短路。
我记得有过一个(OIdalao)讲过一句话。
——如果dp不知道一个状态怎么存，就再加一维。
所以对于正常的一维(SPFA)我们将它加一维，表示当前的能量是多少。最后枚举所有可能的终点能量值即可。
上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<vector>
#include<utility>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define dep(i,n,a) for(int i=n;i>=a;i--)
#define int long long
using namespace std;
queue<pair<int,int> > q;
int n,m,max_energy,dis[55][155],inq[55][55],ans,num,head[55];
struct edge
{
	int u,v,time,energy,nxt;
}e[100050];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return x*f;
}
void add(int u,int v,int t,int en)
{
	e[++num].u=u;e[num].v=v;
	e[num].time=t;e[num].energy=en;
	e[num].nxt=head[u];head[u]=num;
}
signed main()
{
	memset(head,-1,sizeof head);
	memset(dis,127,sizeof dis);
	n=read(),m=read(),max_energy=read();
	int u,v,t,en;
	rep(i,1,m)
	{
		u=read(),v=read(),t=read(),en=read();
		add(u,v,t,en);
	}
	q.push(make_pair(1,max_energy/2));
	ans=dis[0][0];
	dis[1][max_energy/2]=0;
	inq[1][max_energy/2]=1;
	while(!q.empty())
	{
		int x=q.front().first;
		int ee=q.front().second;
		inq[x][ee]=0;
		q.pop();
		for(int st=head[x];~st;st=e[st].nxt)
		{
			int y=e[st].v;
			int ene=e[st].energy;
			if(ee+ene>max_energy||ee+ene<0)continue;
			if(dis[x][ee]+e[st].time<dis[y][ee+ene])
			{
				dis[y][ee+ene]=dis[x][ee]+e[st].time;
				if(!inq[y][ee+ene])
				{
					q.push(make_pair(y,ee+ene));
					inq[y][ee+ene]=1;
				}
			}
		}
	}
	rep(i,0,max_energy)
		ans=min(ans,dis[n][i]);
	printf("%lld",ans);
	return 0;
}