社区讨论

求dalao帮忙看看,一直找不到问题所在

P1576最小花费参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi6m8b7t
此快照首次捕获于
2025/11/20 07:10
4 个月前
此快照最后确认于
2025/11/20 07:10
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int x,y,v[50001];
double dis[50001],n,m,f[2001][2001];
int main()
{
    cin>>n>>m;         //总人数,和可以互相转账人数 
    for(int i=1;i<=n;i++) 
     for(int j=1;j<=n;j++)
       f[i][j]=0x7fffff;
    for(int i=1;i<=m;i++)
      {
          double z;
          cin>>x>>y>>z;
          f[x][y]=f[y][x]=(100-z)/100;  //初始化,预处理 
      }
    for(int i=1;i<=n;i++) 
      {
       dis[i]=0x7fffff; //dis[i]表示i给y100元的最小费 
       v[i]=1;   
      }
    cin>>x>>y;      //以y为起点 
    dis[y]=100;     //dis[i]表示从y到i的花费 
     for(int i=1;i<=n;i++)
    {
        double minn=0x7fff;
        int k;
        for(int j=1;j<=n;j++) 
          if(v[j]&&dis[j]<minn) 
            {
                minn=dis[j];k=j;  //寻找最近蓝点 
            }
        v[k]=0;     //标记为白点 
        for(int j=1;j<=n;j++)
        {
            if(v[j])      //刷新每一个蓝点 
            dis[j]=min(dis[j],dis[k]/f[k][j]);
        }
    }
    printf("%.8lf\n",dis[x]);
return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...