2 条题解
-
0
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e5+10, M=2e5+10, mod=1e9+7; struct edge{int x,y,c,pre;}a[M<<1];int alen=1,last[N],bg[M*2]; void ins(int x,int y,int c) {alen++;a[alen]={x,y,c,last[x]};last[x]=alen;} int n,m,s,t,q,rd[2][N],d[N],pre[N]; LL cnt,b[N],v[N]; LL f[2][N],sum[M],sum2[M],ds[M],dt[M]; void topu(int st, int op) { queue<int> Q; if(!op){memset(d,0x3f,sizeof d);d[st]=0;} f[op][st]=1; for(int i=1;i<=n;i++) if(!rd[op][i]) Q.push(i); while(!Q.empty()) { int x=Q.front();Q.pop(); for(int k=last[x];k;k=a[k].pre)if((k&1)==op) { int y=a[k].y; f[op][y]=(f[op][y]+f[op][x])%mod; if (op==0&&d[y]>d[x]+a[k].c)d[y]=d[x]+a[k].c,pre[y]=k; if (!--rd[op][y]) Q.push(y); } } } int main() { int T;scanf("%d", &T); while(T--) { scanf("%d%d%d%d%d", &n, &m, &s, &t, &q);s++; t++; alen=1;memset(last, 0, sizeof last);memset(rd, 0, sizeof rd); for(int i=1,x,y,z;i<=m;i++) { scanf("%d%d%d", &x, &y, &z);x++; y++; ins(x,y,z);rd[0][y]++; ins(y,x,z);rd[1][x]++; } memset(f, 0, sizeof f);memset(pre, 0, sizeof pre); topu(s,0);if(!f[0][t]) {puts("-1");continue;} topu(t,1); memset(bg, 0, sizeof bg); for(int i=2;i<=alen;i+=2) { int x=a[i^1].y, y=a[i].y; if (f[0][x]*f[1][y]%mod==f[0][t])bg[i]=bg[i^1]=1; } cnt=0;memset(v, 0, sizeof v); for(int z=t;z!=s;z=a[pre[z]].x) { b[++cnt]=a[pre[z]].c; v[cnt]=bg[pre[z]]; } reverse(b+1, b+cnt+1);reverse(v+1, v+cnt+1); memset(sum, 0, sizeof sum);memset(sum2, 0, sizeof sum2); for(int i=1;i<=cnt;i++)sum[i]=sum[i-1]+b[i],sum2[i]=sum2[i-1]+(v[i]?b[i]:0); memset(ds, 0, sizeof ds);memset(dt, 0, sizeof dt); //ds[i]表示从出发点到第i条边的右端点，且只乘车一次下车点是边i的右端点的最小危险程度 //dt[i]表示从结束点到第i条边的左端点，且只乘车一次下车点是边i的左端点的最小危险程度 for(int i=1,j=0;i<=cnt;i++) { while(sum[i]-sum[j]>q) j++; LL t1=ds[i-1]+(v[i]?b[i]:0); LL t2=sum2[j];if(v[j]) t2=t2-( q-(sum[i]-sum[j]) ); ds[i]=min(t1,t2); } for(int i=cnt,j=cnt;i>=1;i--) { while(sum[j]-sum[i-1]>q) j--; LL t1=dt[i+1]+(v[i]?b[i]:0); LL t2=sum2[cnt]-sum2[j];if(v[j+1]) t2=t2-( q-(sum[j]-sum[i-1]) ); dt[i]=min(t1,t2); } LL ans=0x7fffffff; for(int i=0;i<=cnt;i++)//第一次乘车的下车点 和 第二次乘车的上车点不共边，枚举切点(边i的右端点) ans=min(ans, ds[i]+dt[i+1]); for(int i=1,j=0;i<=cnt;i++)//一次乘车的下车点 和 第二次乘车的上车点共边，以2*q为可乘车长度处理一遍 { while(sum[i]-sum[j]>2*q) j++; LL t=sum2[j]+sum2[cnt]-sum2[i];if(v[j]) t=t-(2*q-(sum[i]-sum[j])); ans=min(ans, t); } printf("%lld\n",ans); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:57:02
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e5+10, M=2e5+10, mod=1e9+7; struct edge{int x,y,c,pre;}a[M<<1];int alen=1,last[N],bg[M*2]; void ins(int x,int y,int c) {alen++;a[alen]={x,y,c,last[x]};last[x]=alen;} int n,m,s,t,q,rd[2][N],d[N],pre[N]; LL cnt,b[N],v[N]; LL f[2][N],sum[M],sum2[M],ds[M],dt[M]; void topu(int st, int op) { queue<int> Q; if(!op){memset(d,0x3f,sizeof d);d[st]=0;} f[op][st]=1; for(int i=1;i<=n;i++) if(!rd[op][i]) Q.push(i); while(!Q.empty()) { int x=Q.front();Q.pop(); for(int k=last[x];k;k=a[k].pre)if((k&1)==op) { int y=a[k].y; f[op][y]=(f[op][y]+f[op][x])%mod; if (op==0&&d[y]>d[x]+a[k].c)d[y]=d[x]+a[k].c,pre[y]=k; if (!--rd[op][y]) Q.push(y); } } } int main() { int T;scanf("%d", &T); while(T--) { scanf("%d%d%d%d%d", &n, &m, &s, &t, &q);s++, t++; alen=1;memset(last, 0, sizeof last);memset(rd, 0, sizeof rd); for(int i=1,x,y,z;i<=m;i++) { scanf("%d%d%d",&x,&y,&z);x++, y++; ins(x,y,z);rd[0][y]++; ins(y,x,z);rd[1][x]++; } memset(f, 0, sizeof f);memset(pre, 0, sizeof pre); topu(s,0);if(!f[0][t]) {puts("-1");continue;} topu(t,1); memset(bg, False, sizeof bg); for(int i=2;i<=alen;i+=2) { int x=a[i^1].y, y=a[i].y; if (f[0][x]*f[1][y]%mod==f[0][t])bg[i]=bg[i^1]=1; } cnt=0;memset(v, False, sizeof v); for(int z=t;z!=s;z=a[pre[z]].x) { b[++cnt]=a[pre[z]].c; v[cnt]=bg[pre[z]]; } reverse(b+1, b+cnt+1);reverse(v+1, v+cnt+1); memset(sum, 0, sizeof sum);memset(sum2, 0, sizeof sum2); for(int i=1;i<=cnt;i++)sum[i]=sum[i-1]+b[i],sum2[i]=sum2[i-1]+(v[i]?b[i]:0); memset(ds, 0, sizeof ds);memset(dt, 0, sizeof dt); //ds[i]表示从出发点到第i条边的右端点，且只乘车一次下车点是边i的右端点的最小危险程度 //dt[i]表示从结束点到第i条边的左端点，且只乘车一次下车点是边i的左端点的最小危险程度 for(int i=1,j=0;i<=cnt;i++) { while(sum[i]-sum[j]>q) j++; LL t1=ds[i-1]+(v[i]?b[i]:0);//第i条边不乘车 LL t2=sum2[j];if(v[j]) t2=t2-( q-(sum[i]-sum[j]) );// //第i条边乘车 ds[i]=min(t1,t2); } for(int i=cnt,j=cnt;i>=1;i--) { while(sum[j]-sum[i-1]>q) j--; LL t1=dt[i+1]+(v[i]?b[i]:0); LL t2=sum2[cnt]-sum2[j];if(v[j+1]) t2=t2-( q-(sum[j]-sum[i-1]) ); dt[i]=min(t1,t2); } LL ans=0x7fffffff; for(int i=0;i<=cnt;i++)//第一次乘车的下车点 和 第二次乘车的上车点不共边,枚举切点(边i的右端点) ans=min(ans, ds[i]+dt[i+1]); for(int i=1,j=0;i<=cnt;i++)//一次乘车的下车点 和 第二次乘车的上车点共边，以2*q为可乘车长度处理一遍 { while(sum[i]-sum[j]>2*q) j++; LL t=sum2[j]+sum2[cnt]-sum2[i];if(v[j]) t=t-(2*q-(sum[i]-sum[j])); ans=min(ans, t); } printf("%lld\n",ans); } return 0; }
- 1
