社区讨论
求教不知道思路哪里错了,朴素的bellmanFord
P3063[USACO12DEC] Milk Routing S参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi7dq75m
- 此快照首次捕获于
- 2025/11/20 20:00 4 个月前
- 此快照最后确认于
- 2025/11/20 20:00 4 个月前
#include
#include
#include<stdlib.h>
#define inf 123456
using namespace std;
int u[2010],v[2010],w[2000],l[2000],c[2000],cspot[2000],dis[2000];
int main()
{
int n,m,x;
cin>>n>>m>>x;
for(int i=1;i<=n;i++)
{
dis[i]=inf;
cspot[i]=inf;
}
dis[1]=0;
cspot[1]=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&u[i],&v[i],&l[i],&c[i]);
l[i+m]=l[i];
u[i+m]=v[i];
v[i+m]=u[i];
c[i+m]=c[i];
}
for(int i=1;i<=n-1;i++)
{
int check=0,t=0;
for(int j=1;j<=2*m;j++)
{
//cout<<"1";
if(cspot[u[j]]>c[j])
t=c[j];
else
t=c[u[j]];
if(dis[v[j]]>dis[u[j]]+l[i]+x/t)
{
dis[v[j]]=dis[u[j]]+l[i]+x/t;
cspot[v[j]]=t;
check=1;
}
if(check==0)
break;
}
CPP}
int min=inf;
for(int i=2;i<=n;i++)
if(dis[i]<min)
min=dis[i];
cout<<min;
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...