「萌新刚学oi1秒，90分求调！！」

萌新刚学oi1秒，90分求调！！

板块P4206 [NOI2005] 聪聪与可可
楼主TempestMiku
当前回复5
已保存回复5
发布时间2023/7/23 10:55
上次更新2023/11/3 08:08:19

被骇客银狼阻止的越权访问保存失败

萌新刚学oi1秒，90分求调！！

TempestMiku楼主2023/7/23 10:55

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
    inline int read(){
        int f(1),x(0);
        char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
        return f*x;
    }
    inline void Write(int x){
        if(x>9) Write(x/10);
        putchar(x%10+48);
    }
    inline void write(int x){
        if(x<0) putchar('-'),x=-x;
        Write(x);
        putchar('\n');
    }
}
using namespace Testify;
const int N=1005;
int n,m,cat,mouse;  
int head[N],nxt[N<<1],to[N<<1],tot(0);
int d[N],dis[N][N],op[N][N];
double dp[N][N];//老鼠在i点，猫在j点的期望步数
bool vis[N],visi[N][N];
inline void add(int x,int y){
    to[++tot]=y,nxt[tot]=head[x],head[x]=tot;
    return ;
}
typedef pair<int,int > P;
inline void dij(int now){
    for(register int i=1;i<=n;i++){
        dis[now][i]=INT_MAX;
        vis[i]=0;
    }
    dis[now][now]=0;
    priority_queue<P,vector<P>,greater<P> > q;
    q.push(make_pair(0,now));
    while(q.size()){
        int z=q.top().second;
        q.pop();
        if(vis[z]) continue;
        vis[z]=true;
        for(register int i=head[z];i;i=nxt[i]){
            int y=to[i];
            if(y==z) continue;
            if(dis[now][y]>dis[now][z]+1){
                dis[now][y]=dis[now][z]+1;//权值加1，意思是
                q.push(make_pair(dis[now][y],y));
            }
        }
    }
}
inline double dfs(int mouse,int cat){
    if(visi[mouse][cat]) return dp[mouse][cat];
    if(mouse==cat){
        return 0;
    }
    else if(op[mouse][cat]==mouse||op[mouse][op[mouse][cat]]==mouse){
        return 1;
    }
    else{
        visi[mouse][cat]=true;
        // dp[mouse][cat]++;
        int p=d[mouse]+1;
        dp[mouse][cat]+=(dfs(mouse,op[mouse][op[mouse][cat]])+1)/(1.0*p);
        for(register int i=head[mouse];i;i=nxt[i]){
            int y=to[i];//老鼠跳到的位置
            dp[mouse][cat]+=(dfs(y,op[mouse][op[mouse][cat]])+1)/(1.0*p);
        }
        // cout<<dp[mouse][cat]<<endl;
        return dp[mouse][cat];
    }
}
signed main(void){
    n=read(),m=read(),cat=read(),mouse=read();
    for(register int i=1;i<=m;i++){
        register int asd=read(),jkl=read();
        add(asd,jkl),add(jkl,asd);
        d[asd]++,d[jkl]++;
    }
    for(register int i=1;i<=n;i++){
        dij(i);
    }
    for(register int i=1;i<=n;i++){//老鼠
        for(register int j=1;j<=n;j++){//猫
        if(i==j){continue;}
            int minn=INT_MAX,mindian=INT_MAX;
            for(register int k=head[j];k;k=nxt[k]){//猫跳下一个点
                int y=to[k];
                if(dis[i][y]<minn){
                    op[i][j]=y;
                    minn=dis[i][y];
                    mindian=y;
                }
                else if(dis[i][y]==minn&&y<mindian){
                    op[i][j]=y;
                }
            }
        }
        // puts("");
    }
    printf("%.3lf",dfs(mouse,cat));
    return 0;
}

调了一上午力还是没调出来🥵🥵😰😰😰😰😭😭😭

hack数据输入

输出

12.183

实际输出

12.177

求调😭😭😭😭😭

2023/7/23 10:55