核心思路:
1、 建正反图
2、 topo求最短路及正反路径条数
3、 求桥
4、 获取一条最短路径
5、 dp求两个区间覆盖的最小值。
几个需要注意的点:
1、桥必在s->t的最短路上,先求最短路、及桥。
2、topo时必须加入所有入度为0的点,否则可以达不了终点
3、求桥时使用了两次取模。
4、dp求两个区间覆盖时,分为两个情况:
-
两个区间在一条边上有一部分或全部,此时可以将两个区间当作相邻(一个2*q的区间)来处理。
-
两个区间不在一条边上出现,此时可以通过dp+枚举切点求最小值。
(我见过的最难简单题)
C++ 代码实现(注释有详细说明)
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,inf=1<<29;
typedef long long ll;
const ll mod1=1000000003,mod2=1000000007;
struct Graph{ //图封装
int tot,head[maxn],deg[maxn]; //入度
struct Edge{ int ver,next,w; } edge[maxn];
void add(int u,int v,int w) {
edge[++tot].ver=v; edge[tot].w=w;
edge[tot].next=head[u]; head[u]=tot;
}
}g,rg; //正反图
int dist[maxn],pre[maxn] ;//正图的最短路路径
int bridge[maxn],dis[maxn],val[maxn] ;//一条最短路上的桥、边权、桥的权
int l,n,m,s,t,q,ds[maxn],dt[maxn];
ll fs[maxn][2],ft[maxn][2] ;//正反路径总数,用了两组数据取模
void topo(int st,Graph &g,ll f[][2]) { //求最短路及路径数目
queue<int> que;
for(int i=1;i<=n;i++)//必须将所有入度为0的节点加入,只加入st无法求出最短路
if(g.deg[i]==0) que.push(i);
f[st][0]=f[st][1]=1; //起点初始为0,非起点为0即可
while(que.size()) {
int x=que.front(); que.pop();
for(int i=g.head[x];i;i=g.edge[i].next) {
int y=g.edge[i].ver,w=g.edge[i].w;
if(st==s&&dist[y]>dist[x]+w) { //DAG求最短路
dist[y]=dist[x]+w; pre[y]=i;
} //路径的数目
f[y][0]=(f[y][0]+f[x][0])%mod1;
f[y][1]=(f[y][1]+f[x][1])%mod2;
if(--g.deg[y]==0) que.push(y);
}
} return ;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>l;
while(l--) {
cin>>n>>m>>s>>t>>q; s++,t++;//偏移一位编号
for(int i=0;i<=maxn-3;i++) //初始化
bridge[i]=ft[i][0]=ft[i][1]=fs[i][0]=fs[i][1]=val[i]=0;
g=Graph(); rg=Graph(); //内部变量初始化为0
while(m--) {
int u,v,w;
cin>>u>>v>>w; u++,v++; //编号右移1位
g.add(u,v,w),rg.add(v,u,w); //正反图
g.deg[v]++,rg.deg[u]++;
}
memset(dist,0x3f,sizeof(dist)); dist[s]=0;
topo(s,g,fs);//处理正图 得fs并计算最短路
if(dist[t]>=inf) { //不存在路径
cout<<-1<<endl; continue;
}
topo(t,rg,ft); //处理反图得ft
for(int x=1;x<=n;x++) { //获得桥
for(int i=g.head[x];i;i=g.edge[i].next) {
int y=g.edge[i].ver;
if(fs[x][0]*ft[y][0]%mod1==fs[t][0]&&fs[x][1]*ft[y][1]%mod2==fs[t][1])
bridge[i]=1;
}
} //获取路径(反向的)
int x=t,cnt=0;
while(x!=s) {
int i=pre[x];
dis[++cnt]=g.edge[i].w; //储存的为边的边权
if(bridge[i]) val[cnt]=g.edge[i].w;
x=rg.edge[i].ver;//用反图求出边i的起点
}
for(int i=1;i<=cnt;i++) //获得前缀和
val[i]+=val[i-1],dis[i]+=dis[i-1];
//动态规划:ds[j]=min{上车区间是前面的,上车区间以j为终点}
for(int i=0,j=1;j<=cnt;++j) {
ds[j]=ds[j-1]+val[j]-val[j-1]; //上车区间是前面的
while(dis[j]-dis[i]>q) i++;
//i边为桥、 上车区间以j为终点
if(i!=0&&val[i]-val[i-1])//覆盖i边的一部分及i~j的全部
ds[j]=min(ds[j],val[i]-(q-dis[j]+dis[i]));
else ds[j]=min(ds[j],val[i]) ; //覆盖i~j部分,i边覆盖与否不影响答案
} //反向处理同理
for(int i=cnt-1,j=cnt;i>=0;i--) {
dt[i]=dt[i+1]+val[i+1]-val[i];
while(dis[j]-dis[i]>q) j--;
if(j!=cnt&&val[j+1]-val[j])
dt[i]=min(dt[i],val[cnt]-val[j]-(q-dis[j]+dis[i]));
else dt[i]=min(dt[i],val[cnt]-val[j]);
}
int ans=inf;
for(int i=0;i<=cnt;i++) //不共边,枚举切点
ans=min(ans,ds[i]+dt[i]);
for(int i=0,j=1;j<=cnt;j++) { //共边,以2*q为可乘车长度处理一遍
while(dis[j]-dis[i]>2*q) i++; //核心思想为:枚举以j为下车点的结果
if(i!=0&&val[i]-val[i-1]) //为桥
ans=min(ans,val[i]-(q*2-dis[j]+dis[i])+val[cnt]-val[j]);
else ans=min(ans,val[i]+val[cnt]-val[j]); //在i~j之间都乘车
} cout<<ans<<endl;
}
return 0;
}