poj 1062 昂贵的聘礼（floyd path的应用）
2024-09-01 06:06:49
题目链接：http://poj.org/problem?id=1062
题意就不解释了中问题。
这题用dfs也行。但是感觉还是floyd比较好一点主要是他们交易是有条件的交易总的等级差不能超过m
所以这时floyd中path的属性就用到了，path[i][j].MAX表示i交易到j最大等级是多少path[i][j].MIN表示最小等级是多少
然后接下来就简单了。
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#define inf 0X3f3f3f3f
using namespace std;
int n , m , p , l[110] , x[110] , t[110][110] , v , val[110] , dis[110][110];
struct TnT {
int MAX , MIN;
}path[110][110];
int Abs(int x , int y) {
if(x > y)
return x - y;
else
return y - x;
}
void floyd() {
for(int k = 1 ; k <= n ; k++) {
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= n ; j++) {
if(dis[i][j] > dis[i][k] + dis[k][j] && Abs(path[i][k].MAX , path[k][j].MIN) <= m && Abs(path[i][k].MIN , path[k][j].MAX) <= m) {
dis[i][j] = dis[i][k] + dis[k][j];
path[i][j].MAX = max(path[i][k].MAX , path[k][j].MAX);
path[i][j].MIN = min(path[i][k].MIN , path[k][j].MIN);
}
}
}
}
}
int main() {
while(cin >> m >> n) {
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= n ; j++) {
path[i][j].MAX = n + 1;
path[i][j].MIN = 0;
dis[i][j] = inf;
}
dis[i][i] = 0;
}
for(int i = 1 ; i <= n ; i++) {
cin >> p >> l[i] >> x[i];
val[i] = p;
path[i][i].MAX = l[i];
path[i][i].MIN = l[i];
for(int j = 1 ; j <= x[i] ; j++) {
cin >> t[i][j] >> v;
dis[i][t[i][j]] = v;
}
}
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= x[i] ; j++) {
if(Abs(l[i] , l[t[i][j]]) <= m) {
path[i][t[i][j]].MAX = max(l[i] , l[t[i][j]]);
path[i][t[i][j]].MIN = min(l[i] , l[t[i][j]]);
}
else {
dis[i][t[i][j]] = inf;
}
}
}
floyd();
int MIN = inf;
for(int i = 1 ; i <= n ; i++) {
MIN = min(MIN , dis[1][i] + val[i]);
}
cout << MIN << endl;
}
return 0;
}
最新文章
- Flesch Reading Ease -POJ3371模拟
- C++ 类、构造析构、深拷贝
- Eclipse: JPA problem: Eclipse does not recognize content of persistence.xml
- 工厂方法模式与IoC/DI控制反转和依赖注入
- JavaScript中的原型继承原理
- 记录最近的几个bug
- 实现自己的HashMap
- class example of C++
- PLA-1
- 注册一个gitHub
- spring对bean的高级装配之profile机制
- rgb & rgba convert
- 尚硅谷redis学习1-NOSQL简介
- SD从零开始11-12
- iOS国际化——通过脚本使storyboard翻译自增
- Sony/索尼 NW-ZX300A ZX300 无损音乐播放器4.4口
- D:\hunting2014\小题目\字符串倒序
- CSS3的新增边框属性
- ios NSString format 保留小数点 float double
- Java中数组转为List三种情况的优劣对比，常犯的类型转换错误原因解析