题目描述:
给定一个包含 n 个点的简单无向完全图,每条边有给定的权重。对于指定的起点和终点,求一条从起点到终点的路劲值最大的路径。 路径的路劲值定义为:这条路径上所有边的权重的最小值除以路径包含的边数。 符合条件的路径可能不唯一,但是其路劲值肯定唯一,输出这个值。
输入格式:
第一行三个整数表示图中的点数和指定的起点和终点 n、s、t(节点编号为 1 到 n,2 <= n <= 100,1 <= s < t <= n)。
接下来 n - 1 行为所有边的权重。其中第 i 行会有 n - i 个数,第 j 个数为 i 号节点到 i + j 号节点的边的权重W[i,i+j](0 <= W[i,i+j] <= 1000000)。
输出格式:
输出一个实数,为要求的最大路劲值,保留两位小数。
样例
输入
4 2 3 3 4 7 1 5 6
输出
2.50
我的代码(马峰差,莫喷
#include<bits/stdc++.h>
#define int long long
#define p pair<int,int>
#define m(a,b) make_pair(a,b)
using namespace std;
inline int read(){int f=1,x=0;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void write(int x){if (x<0){putchar('-');x=-x;}if(x>9) write(x/10);putchar(x%10+'0');}
inline void Write(int x){write(x);putchar('\n');}
const int N=105,M=10005,inf=0x7fffffff;
int n,s,t,head[N],vis[N],viss[N],dis[N],diss[N],cnt=0;
double ans=-inf;
struct edge{
int u,v,w,nxt;
}e[M<<1];
void add(int u,int v,int w){
e[++cnt]={u,v,w,head[u]};
head[u]=cnt;return;
}
void init(){
for (int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;
return;
}
void dijk(int x,int ww){
init();
dis[x]=0;
priority_queue<p,vector<p>,greater<p> > q;
q.push({0,x});
while (!q.empty()){
int g=q.top().second;
q.pop();
if (vis[g])continue;
vis[g]=1;
for (int i=head[g];i!=-1;i=e[i].nxt){
int h=e[i].v,hw=e[i].w;
if (vis[h]||(hw<ww))continue;
if (dis[g]+1<dis[h]){
dis[h]=dis[g]+1;
q.push({dis[h],h});
}
}
}
return;
}
void initt(){
for (int i=1;i<=n;i++)diss[i]=inf,viss[i]=0;
return;
}
void dijkk(int x,int ww){
initt();
diss[x]=0;
priority_queue<p,vector<p>,greater<p> > q;
q.push({0,x});
while (!q.empty()){
int g=q.top().second;
q.pop();
if (viss[g])continue;
viss[g]=1;
for (int i=head[g];i!=-1;i=e[i].nxt){
int h=e[i].v,hw=e[i].w;
if (viss[h]||(hw<ww))continue;
if (diss[g]+1<diss[h]){
diss[h]=diss[g]+1;
q.push({diss[h],h});
}
}
}
return;
}
void solve(int x){
dijk(e[x].u,e[x].w),dijkk(e[x].v,e[x].w);
ans=max(ans,double(e[x].w)/(dis[s]+diss[t]));
}
signed main(){
n=read(),s=read(),t=read();
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++){
int w=read();
add(i,j,w);add(j,i,w);
}
for (int i=1;i<=cnt;i++)solve(i);
printf("%.2lf",ans);
return 0;
}
请问各位为什么没有输出