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


迷路(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\) 的能量。保

证,\(1\leq u,v\leq n,1\leq time\leq 10^4 ,−100\leq energy\leq 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

【子任务】

每个测试点的数据规模如下

\(1\)\(5\)\(11\)\(4\)无特殊性质
\(2\)\(8\)\(16\)\(4\)无特殊性质
\(3\)\(10\)\(21\)\(6\)无特殊性质
\(4,5,6\)\(50\)\(2000\)\(10^2\)所有的\(energy\)均为正
\(7,8,9,10\)\(50\)\(2000\)\(50\)无特殊性质

容易想到最短路。但是因为有\(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;
}
05-08 08:21