Luogu P1730 最小密度路径

题目链接https://www.luogu.org/problemnew/show/P1730

题意:略。

思路dfs暴力预处理即可,也可借鉴floyd的思想,定义dp[i][j][l]i->j恰好经过l条路的最短路,则转移方程为dp[i][j][l]=min(dp[i][j][l-1]+dp[i][j][1]),询问的时候枚举边长度更新答案即可,时间复杂度O(n^4)

爆搜

const int N=50+10;
int n,m,i,j,u,v,w,Q,x,y;
double ans[N][N];
vector<pair<int,int> >G[N];
void dfs(int root,int u,int w,int cnt){
    if (u!=root){
        double tmp=w*1.0/cnt;
        ans[root][u]=ans[root][u]==-1?tmp:min(ans[root][u],tmp);
    }
    for (int i=0;i<(int)G[u].size();i++){
        pair<int,int> cur=G[u][i];
        int v=cur.first,ww=cur.second;
        dfs(root,v,w+ww,cnt+1);
    }
}
int main(){
    read(n),read(m);
    for (i=1;i<=n;i++)for (j=1;j<=n;j++)ans[i][j]=(i==j?0:-1);
    for (i=1;i<=m;i++){
        read(u),read(v),read(w);
        G[u].pb(mp(v,w));
    }
    for (i=1;i<=n;i++){
        dfs(i,i,0,0);
    }
    for (read(Q);Q--;){
        read(x),read(y);
        if (ans[x][y]==-1) puts("OMG!");
        else printf("%.3lf\n",ans[x][y]);
    }
    return 0;
}

DP

const int N=50+10;
const int M=1000+10;
int n,m,l,i,j,k,q,u,v,w,dp[N][N][M];
void umin(int&a,int b){if(a>b)a=b;}
int main(){
    read(n),read(m);
    for (l=1;l<=m;l++)for(i=1;i<=n;i++)for(j=1;j<=n;j++) dp[i][j][l]=(int)1e9;
    for (i=1;i<=m;i++){
        read(u),read(v),read(w);
        umin(dp[u][v][1],w);
    }
    for (l=2;l<=m;l++)for(k=1;k<=n;k++){
        for(i=1;i<=n;i++)for(j=1;j<=n;j++){
            umin(dp[i][j][l],dp[i][k][l-1]+dp[k][j][1]);
        }
    }
    for (read(q);q--;){
        read(u),read(v);
        double ans=1e9;
        for (i=1;i<=m;i++){
            if (dp[u][v][i]<1e9 && 1.0*dp[u][v][i]/i<ans) ans=min(ans,1.0*dp[u][v][i]/i);
        }
        if (ans==1e9) puts("OMG!");
        else printf("%.3lf\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注