udebug上第一个数据,第一篇题解是WA的,case 97输出的是391.63,答案是391.62(我也错了,想拿题解拍一下,不是抄题解),但是提交是AC的?这是什么原因,但是我的提交是WA的,附上代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int t,n,m,head[55],nxt[3005],to[3005],a[3005],cnt,b[55],vis[55];
double dis[55];
void add(int u,int v,int w){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
a[cnt]=w;
}
bool check(double x){
memset(b,0,sizeof(b));
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
queue<int> q;
for(int i=1;i<=n;i++){
q.push(i);
vis[i]=1;
}
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]>dis[u]+a[i]-x){
dis[v]=dis[u]+a[i]-x;
b[v]++;
if(b[v]>=n)return 1;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return 0;
}
int main(){
cin>>t;
for(int ca=1;ca<=t;ca++){
memset(head,0,sizeof(head));
memset(nxt,0,sizeof(nxt));
memset(a,0,sizeof(a));
memset(to,0,sizeof(to));
cnt=0;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
double l=0,r=1e7+1;
while(r-l>1e-4){
double mid=(l+r)/2;
if(check(mid)){
r=mid;
}else{
l=mid;
}
}
if(r==1e7+1){
printf("Case #%d: No cycle found.\n",ca);
}else{
printf("Case #%d: %.2lf\n",ca,r);
}
}
return 0;
}