「2017 山东一轮集训 Day6」重建 题解
prob。
之前一场模拟赛的 T4，赛时用 Dijkstra 预处理 \(f,g\)，判断还写挂了，喜提 \(30\) 分。
考虑 \(f_{u,k}\) 表示从 \(s\) 走到 \(u\) 并且经过恰好 \(0\le k\le n\) 条边的最短路，则当每条边加上 \(c\) 时，该路径长度变为 \(f_{u,k}+kc\)。
设 \(g_{u,k}\) 表示从 \(s\) 走到 \(u\)，经过恰好 \(k\) 条边并且只经过关键点的最短路。若想让 \(g_{t,k}\) 成为 \(s\) 到 \(t\) 的最短路，则要选择合适的 \(c\) 满足 \(\forall 0\le i\le n,g_{t,k}+kc\le f_{t,i}+ic\)。
分类讨论：
-
若 \(k< i\)，则需要使 \(c \ge\dfrac{g_{t,k}-f_{t,i}}{i-k}\)。
-
若 \(k=i\)，判断是否满足 \(g_{t,k}\le f_{t,i}\)。
-
若 \(k>i\)，则需要使 \(c\le \dfrac{f_{t,i}-g_{t,k}}{k-i}\)。
于是限制了 \(c\) 的上下界。对于所有 \(g_{t,k}\) 算一遍，找到最大的合法右端点即可。
\(f,g\) 可以使用类似 Bellman-Ford 的方式求出。
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
const ll maxn=1007,p=1e9+7,ee=2e18;
ll n,m,s,t,k,stt[maxn],d[maxn],cnt[maxn],dis[2][maxn][1007],ans;
bool vis[maxn];
vector<pair<ll,ll> > edge[maxn];
ll calc(ll k1,ll b1){
ll k2,b2,mx=0,mn=ee;
for(int i=0;i<=n;i++)if(dis[0][t][i]<ee){
k2=i,b2=dis[0][t][i];
if(b1==b2&&k1==k2) continue;
if(b2<b1&&k2==k1) return -1;
if(b2>b1&&k2==k1) continue;
if(b2<=b1){
if(k2<k1) return -1;
else mx=max(mx,(ll)ceil(1.0*(b2-b1)/(k1-k2)));
}else if(k2<k1) mn=min(mn,(b2-b1)/(k1-k2));
}
return (mn<mx?-1:mn);
}
int main(void){
ios::sync_with_stdio(0),cin.tie(0);
ll T=1; cin>>T;
for(;T--;){
for(int i=1;i<=n;i++) stt[i]=0,edge[i].clear();
cin>>n>>m>>s>>t;
memset(dis,0x3f,sizeof(dis));
for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,edge[u].pb(v,w),edge[v].pb(u,w);
cin>>k;
for(int i=1,a;i<=k;i++) cin>>a,stt[a]=1;
dis[0][s][0]=dis[1][s][0]=0;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
for(auto x:edge[j]) dis[0][j][i]=min(dis[0][j][i],dis[0][x.first][i-1]+x.second);
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
for(auto x:edge[j]){
if(!stt[x.first]) continue;
dis[1][j][i]=min(dis[1][j][i],dis[1][x.first][i-1]+x.second);
}
}
ans=-1;
for(int i=0;i<=n;i++)if(dis[1][t][i]<ee) ans=max(ans,calc(i,dis[1][t][i]));
if(ans==-1) cout<<"Impossible\n";
else if(ans>=ee) cout<<"Infinity\n";
else cout<<ans<<"\n";
}
return 0;
}