最后一个点TLE了Bellman_ford算法
  • 板块P1396 营救
  • 楼主Jessica2333
  • 当前回复14
  • 已保存回复14
  • 发布时间2022/1/14 19:20
  • 上次更新2023/10/28 12:22:04
查看原帖
最后一个点TLE了Bellman_ford算法
444063
Jessica2333楼主2022/1/14 19:20

这道题用Bellman_ford不行吗??求大佬指导!!```cpp

#include<iostream>
using namespace std;
long long n,m,dist[20000],Max=2147483647;
struct{
	long long u,v,w;
}bb[20000];
void Bellman_ford(long long s)
{
	long long i,j,k;
	for(j=1;j<=n;j++)
	{
		for(i=1;i<=m;i++)
		{
			dist[bb[i].v]=min(dist[bb[i].v],max(dist[bb[i].u],bb[i].w));
			dist[bb[i].u]=min(dist[bb[i].u],max(dist[bb[i].v],bb[i].w));
		}
	}
}
int main()
{
	long long a,b,c,i,j,k,st,end;
	cin>>n>>m>>st>>end;
	for(i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		bb[i].u=a;
		bb[i].v=b;
		bb[i].w=c;
	}
	for(i=1;i<=n;i++) dist[i]=Max;
	dist[st]=0;
	Bellman_ford(st);
	cout<<dist[end];
}
2022/1/14 19:20
加载中...