社区讨论
求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 条回复,欢迎继续交流。
正在加载回复...