http://blog.csdn.net/lyhvoyage/article/details/19281013这篇博文的Bellman-Ford 算法代码里面的松弛操作的一部分:
for(int i = 1; i <= n - 1; i++)
{
bool flag = false;
for(int j = 0; j < C; j++)
{
int a = p[j].a, b = p[j].b;
double r = p[j].rate, c = p[j].cost;
if(dis[b] < (dis[a] - c) * r)
{
dis[b] = (dis[a] - c) * r;
flag = true;
}
}
if(!flag)
break;
这里为什么加一个flag变量呢?
我把flag去掉了一样可以AC, 并且时间也是0ms, 不是很理解作者在这里加flag的意图.
对于Bellman-Ford算法还是不怎么理解, 希望有人帮忙解惑一下.
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
https://www.v2ex.com/t/128551
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.