关于第一篇题解
查看原帖
关于第一篇题解
633466
LiaoYF1楼主2023/9/3 20:46

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;
}
2023/9/3 20:46
加载中...