POJ Layout
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
Some cows like each other and want to be within a certain distance
of each other in line. Some really dislike each other and want to be
separated by at least a certain distance. A list of ML (1 <= ML <=
10,000) constraints describes which cows like each other and the
maximum distance by which they may be separated; a subsequent list of MD
constraints (1 <= MD <= 10,000) tells which cows dislike each
other and the minimum distance by which they must be separated.
Your job is to compute, if possible, the maximum possible distance
between cow 1 and cow N that satisfies the distance constraints.
Input
Lines 2..ML+1: Each line contains three space-separated positive
integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must
be at most D (1 <= D <= 1,000,000) apart.
Lines ML+2..ML+MD+1: Each line contains three space-separated
positive integers: A, B, and D, with 1 <= A < B <= N. Cows A
and B must be at least D (1 <= D <= 1,000,000) apart.
Output
1: A single integer. If no line-up is possible, output -1. If cows 1
and N can be arbitrarily far apart, output -2. Otherwise output the
greatest possible distance between cows 1 and N.
Sample Input
4 2 1
1 3 10
2 4 20
2 3 3
Sample Output
27
Hint
There are 4 cows. Cows #1 and #3 must be no more than 10 units
apart, cows #2 and #4 must be no more than 20 units apart, and cows #2
and #3 dislike each other and must be no fewer than 3 units apart.
The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 9999999 int dis[1010];
int cnt;
int n, ml, md; struct N
{
int u;
int v;
int w;
}s[200005]; void add(int u, int v, int w )
{
s[cnt].u=u;
s[cnt].v=v;
s[cnt++].w=w;
} void bellman_ford()
{
int i, j;
for(i=1; i<=n; i++)
dis[i]=INF;
dis[1]=0; for(i=2; i<=n; i++ )
{
int flag=0;
for(j=0; j<cnt; j++ ) //检查每条边
{
if( dis[s[j].v] > dis[s[j].u] + s[j].w )
{
dis[s[j].v] = dis[s[j].u]+s[j].w ;
flag=1;
}
}
if(flag==0)
break;
}
for(i=0; i<cnt; i++)
{
if(dis[s[i].v] > dis[s[i].u]+s[i].w )
break;
}
if(i<cnt)
printf("-1\n");
else
{
if( dis[n]==INF )
printf("-2\n");
else
printf("%d\n", dis[n] );
}
} int main()
{
int i, j;
int u, v, w;
while(scanf("%d %d %d", &n, &ml, &md)!=EOF)
{
cnt=0;
for(i=0; i<ml; i++)
{
scanf("%d %d %d", &u, &v, &w ); //亲密的牛 最大距离
if(u>v)
{
u=u^v; v=v^u; u=u^v; //还可以这样写: u^=v^=u^=v ;
}
add(u, v, w);
}
for(j=0; j<md; j++)
{
scanf("%d %d %d", &u, &v, &w ); //排斥的牛 最小距离
if(u<v)
{
u=u^v; v=v^u; u=u^v; // u^=v^=u^=v ;
}
add(u, v, -w);
}
bellman_ford();
}
return 0;
}
最新文章
- Oracle 语句常见错误
- HTTP缓存ETAG和Last-Modified
- SQL 查找存储过程及视图与自带函数
- Ubuntu 12.04和Windows 7双系统安装图解
- TCP和UDP协议的区别
- 排序算法的C语言实现(上 比较类排序:插入排序、快速排序与归并排序)
- apache环境下ssl证书链不完整问题解决,原因是缺少中间证书
- [转]调整 VirtualBox 虚拟机的磁盘大小
- golang 无法将Slice类型[]a 转换为 Slice[]b
- 学习笔记之Machine Learning Crash Course | Google Developers
- 装CentOS 系统
- SEO经验-如何做到新站上线半个月谷歌收录3万
- vs2013添加mysql对EF的支持(转+说明)
- ALGO-9_蓝桥杯_算法训练_摆动序列(DP)
- linux 时间相关的一些总结
- SuperSlide轮播插件滚动高度或宽度不对的问题解决
- 用Copy命令合并文件
- BZOJ5073 小A的咒语(动态规划)
- Sprint第一个冲刺(第七天)
- [转]微信小程序-template模板使用
热门文章
- 介绍C#结构体与类区别
- inotify+rsync
- Git--Bug解决篇
- inside when() you don&#39;t call method on mock but on some other object
- [译]NeHe教程 - 创建一个OpenGL窗体
- yaffs2在am335x上实施
- PHP运行环境之IIS FastCGI 进程意外退出解决办法
- ubuntu openfire Server install
- Xcode 5、Xcode 6 免证书真机调试
- python语言特性-------python2.7教程学习【廖雪峰版】(一)