Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
151136 | 吴宗桦 | 最佳牧场 | C++ | 通过 | 100 | 202 MS | 1240 KB | 694 | 2024-06-12 13:13:36 |
#include<bits/stdc++.h> using namespace std; int p,f,c,e[501][501],ff[501],u,v,w,ans; double s,fs=DBL_MAX; int main() { cin>>p>>f>>c; for(int i=1;i<=p;i++) for(int j=1;j<=p;j++) e[i][j]=(i!=j)*INT_MAX; for(int i=1;i<=f;i++) cin>>ff[i]; for(int i=1;i<=c;i++) cin>>u>>v>>w,e[u][v]=e[v][u]=w; for(int k=1;k<=p;k++) for(int i=1;i<=p;i++) for(int j=1;j<=p;j++) if(i!=j&&j!=k&&j!=k&&e[i][k]<INT_MAX&&e[k][j]<INT_MAX) e[i][j]=min(e[i][j],e[i][k]+e[k][j]); for(int i=1;i<=p;i++) { s=0; for(int j=1;j<=f;j++) { if(e[i][ff[j]]<INT_MAX) s+=e[i][ff[j]]; else break; } if(fs>s/f) ans=i,fs=s/f; } cout<<ans; }