2022 Hubei Provincial Collegiate Programming Contest

A     Nucleic Acid Test

题目大意：给你n个点，m条边，其中k个点为急救站，你可以从任意一个急救站出发，一条路径可以重复走，但要在满足到达下一个急救站之前所走的路径S,除以速度V得到的时间小于等于t的情况下，走完每一个点，求出满足条件的最小的速度v。

思路：看数据范围n<=300，很快就可以想到要用floyd计算出两点之间的距离（vp的时候被队友说时间复杂度过高，说换个算法。。。事实证明不应该听队友的），要使速度最小，路程就要最小，我们直接算出非急救站的点到最近的急救站的距离，这样一来一回可以使路程最小，然后在所有非急救站中选一个最大值，然后急救站之间也要连通，所以用最小生成树，可以计算出最大边，然后就可以得到结果了。

Code:

const int N=1e5+5,mod=998244353;
const int inf=1e18;
int n,m,k,h[305];
bool mp[310];
int find(int i)
{if(h[i]!=i) h[i]=find(h[i]);return h[i];
}
struct node{int a,b,c;bool operator<(const node&l)const{return c<l.c; }
}tr[310*310];void solve()
{cin>>n>>m>>k;int t;cin>>t;if(t==0){cout<<-1;return ;}vector<vector<int>> dist(n+1,vector<int>(n+1,1e18));for(int i=1;i<=n;i++) dist[i][i]=0,h[i]=i;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;dist[b][a]=dist[a][b]=min(c,dist[a][b]);}for(int i=1;i<=k;i++){int x;cin>>x;mp[x]=1;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int y=1;y<=n;y++){dist[j][y]=min(dist[j][y],dist[j][i]+dist[i][y]);}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (dist[i][j] > (inf / 2)) {cout << "-1";return ;}       }}int ma1=0;for(int i=1;i<=n;i++){if(mp[i]) continue;int mn=1e18;for(int j=1;j<=n;j++){if(mp[j])mn=min(dist[i][j]*2,mn);}ma1=max(ma1,mn);}int k1=0;for(int i=1;i<=n;i++){if(mp[i])for(int j=i+1;j<=n;j++){// if(i==j) continue;if(mp[j]&&dist[i][j]<(inf/2))tr[k1++]={i,j,dist[i][j]};}}sort(tr,tr+k1);for(int i=0;i<k1;i++){int pa=find(tr[i].a),pb=find(tr[i].b),c=tr[i].c;if(pa!=pb){h[pa]=pb;ma1=max(ma1,c);}}cout<<(ma1+t-1)/t;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;//cin>>t;t=1;while(t--) solve();
}