POJ-3259 Wormholes (ballman_ford 判负环)
2024-10-06 12:16:41
ballman_ford 是对单源点到任意点最短路的处理方法(可以含负权边)。
对所有边进行n-1次循环,(n为点得个数),如果此时源点到这条边终点的距离 大于 源点到这条边起点的距离加上路得权值就进行更新。
题意:FJ农场主有F个农场, 在每个农场内有 N个点, M条双向路, W个单向虫洞, 每条路需要消耗一定的时间, 每个虫洞可以使得自己回到几秒前, 现在问FJ农场主可不可以遇到以前的自己。
题解: ballman_ford 判断负环, 存在负环就说明可以, 不存在就不可以。
#include<iostream>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = , M = , W = ;
struct Node
{
int u, v, d;
}e[M*+W];
int dis[N];
int cnt = , n, m, w;
void add(int u, int v, int d)
{
e[cnt].u = u;
e[cnt].v = v;
e[cnt++].d = d;
}
bool ballman_ford()
{
memset(dis, INF, sizeof(dis));
dis[] = ;
for(int i = ; i < n; i++)
for(int j = ; j < cnt; j++)
{
if(dis[e[j].v] > dis[e[j].u] + e[j].d )
{
dis[e[j].v] = dis[e[j].u] + e[j].d;
}
}
bool flag = ;
for(int i = ; i < cnt; i++)
{
if(dis[e[i].v] > dis[e[i].u] + e[i].d)
{
flag = ;
break;
}
}
return flag;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int T;
cin >> T;
while(T--)
{
cnt = ;
cin >> n >> m >> w;
int u, v, d;
for(int i = ; i < m; i++)
{
cin >> u >> v >> d;
add(u, v, d);
add(v, u, d);
}
for(int i = ; i < w; i++)
{
cin >> u >> v >> d;
add(u, v, -d);
}
if(!ballman_ford()) cout << "YES\n";
else cout << "NO\n";
}
return ;
}
最新文章
- ActiveMQ在Linux中的安装
- Thinkphp文件上传
- C# 以附加文件方式连接SQL Server数据库文件
- 【C#】分享一个可灵活设置边框的Panel
- IOS开发之WIFI及IP相关
- 用form表单实现Ajax---post提交
- Ajax如何实现跨域问题
- C语言培训第一天
- hadoop面试时可能遇到的问题
- SQL server 2012 如何取上个月的最后一天
- java多线层同时运行的解决,同步代码块synchronized
- 【持续集成】GIT+jenkins+snoar——jenkins发布php、maven项目
- 201521044091 《Java程序设计》第3周学习总结
- Owin学习笔记(一) Owin的前生今世
- Go语言从入门到放弃(一) 变量/常量/函数
- tensorflow实战系列(二)TFRecordReader
- Alpha阶段敏捷冲刺---Day7
- MyBatis批量操作报错:Parameter &#39;xxxList&#39; not found. Available parameters are [list]
- php composer,update-ca-trust
- WCF问题集锦:未依照DataMember定义的名称序列化对象