某些题解代码冗长,不想看,于是自己写了一份更为简洁的代码
只有不到120行,如果去掉读入优化和宏定义会更短,仅供大家参考
有两个值得注意的地方,1是节点标号是0到n-1,2是DP时细节很多需要注意,尤其是边界问题和在一条边的中途上车的情况的判断
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f,N=1e5+10,mod[2]={(int)999983,1226959};
typedef int aray[N];
typedef long long ll;
int n,m,s,t,q,cnt=0,cnt2=0,fs[N][2],ft[N][2],tot;
bool brg[4*N];
aray head,rhead,ind,outd,pre,d,dis,ds,dt,val;
struct edge{
int nxt,v,w;
}e[4*N],re[4*N];
void add(int u,int v,int w){
e[cnt]=(edge){head[u],v,w};
head[u]=cnt++;
}
void radd(int u,int v,int w){
re[cnt2]=(edge){rhead[u],v,w};
rhead[u]=cnt2++;
}
void read(int &x){
x=0;char c=getchar(),f=1;
while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
x*=f;
}
void topsort(int s,edge e[],int head[],int ind[],int f[][2],bool op){
queue<int>q;
q.push(s);
f[s][0]=f[s][1]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i+1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(op==0&&d[v]>d[u]+w){
d[v]=d[u]+w;
pre[v]=i;
}
f[v][0]=(f[v][0]+f[u][0])%mod[0];
f[v][1]=(f[v][1]+f[u][1])%mod[1];
if(--ind[v]==0) q.push(v);
}
}
}
void init(){
cnt=0,cnt2=0;tot=0;
mem(fs,0);mem(ft,0);mem(ind,0);mem(outd,0);mem(val,0);
mem(brg,0);mem(head,-1),mem(rhead,-1);
}
void work(){
init();
read(n),read(m),read(s),read(t),read(q);
int u,v,w;
go(i,1,m){
read(u),read(v),read(w);
add(u,v,w);
radd(v,u,w);
++ind[v],++outd[u];
}
mem(d,0x3f);d[s]=0;
topsort(s,e,head,ind,fs,0);
if(d[t]==inf){
puts("-1");
return;
}
topsort(t,re,rhead,outd,ft,1);
go(u,0,n-1)
for(int i=head[u];i+1;i=e[i].nxt){
int v=e[i].v;
if(1ll*fs[u][0]*ft[v][0]%mod[0]==fs[t][0]&&1ll*fs[u][1]*ft[v][1]%mod[1]==fs[t][1]) brg[i]=1;
}
int x=t;
while(1){
if(x==s) break;
int i=pre[x];
dis[++tot]=e[i].w;
if(brg[i]) val[tot]=e[i].w;
x=re[i].v;
}
go(i,1,tot) val[i]+=val[i-1],dis[i]+=dis[i-1];
for(int i=0,j=1;j<=tot;++j){
ds[j]=ds[j-1]+val[j]-val[j-1];
while(dis[j]-dis[i]>q) ++i;
if(i!=0&&val[i]-val[i-1]) ds[j]=min(ds[j],val[i]-(q-dis[j]+dis[i]));//如果是桥
else ds[j]=min(ds[j],val[i]);
}
for(int i=tot-1,j=tot;i>=0;--i){
dt[i]=dt[i+1]+val[i+1]-val[i];
while(dis[j]-dis[i]>q) --j;
if(j!=tot&&val[j+1]-val[j]) dt[i]=min(dt[i],val[tot]-val[j]-(q-dis[j]+dis[i]));
else dt[i]=min(dt[i],val[tot]-val[j]);
}
int ans=INT_MAX;
go(i,0,tot)
ans=min(ans,ds[i]+dt[i]);
printf("%d\n",ans);
}
int main(){
int T;read(T);
while(T--) work();
return 0;
}
正确答案显然是$1$
您的代码也解决不了这个问题啊,这个问题只能特判
震惊,惊现
机房绿太阳
(已举报以搞煌为主业的mzg1806)ds(i)和dt(i)在lyd的原书上表示到达i节点的最小危险程度,并不能处理起点和终点在一条边的中间的情况
#震惊!
吊打集训队竟然在此发题解
被发现了
(逃)$Hack$数据
我们互踩不太好吧,还是互赞比较好