差分约束第一题。
所有的条件无非两种不等式
$d[i]-d[j]>=dist$
$d[i]-d[j]<=dist$
然后进行变形
$d[i]-d[j]>=dist$ $=>$ $d[j]<=d[i]-dist$ $=>$ $insert(i,j,-dist)$
$d[i]-d[j]<=dist$ $=>$ $d[i]<=d[j]+dist$ $=>$ $insert(j,i,dist)$
$d[i]+0>=d[i-1]$ $=>$ $insert(i,i-1,0)$
由此可以建图
最后需要注意两个点:
1.如何判断-1?
-1是无解的情况,什么是无解?显然是存在负环的情况。
2.如何判断-2?
当$ans==oo$时,就应输出-2,因为如果最小的距离是无穷大那么显然取任何值都可以。
//COGS 1117 //by Cydiater //2016.9.1 #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <iomanip> #include <cmath> #include <ctime> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) #define FILE "layout" ; const int oo=0x3f3f3f3f; inline ll read(){ ,f=; ;ch=getchar();} +ch-';ch=getchar();} return x*f; } ll N,Ma,Mb,LINK[MAXN],len=,head,tail,q[MAXN],dis[MAXN],cnt[MAXN]; bool vis[MAXN]; struct edge{ int y,next,v; }e[MAXN]; namespace solution{ inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;} void init(){ N=read();Ma=read();Mb=read(); up(i,,Ma){ ll x=read(),y=read(),dist=read(); if(x>y)swap(x,y); insert(x,y,dist); } up(i,,Mb){ int x=read(),y=read(),dist=read(); if(x>y)swap(x,y); insert(y,x,-dist); } up(i,,N)insert(i,i-,); } void SPFA(){ memset(vis,,sizeof(vis)); memset(cnt,,sizeof(cnt)); up(i,,N)dis[i]=oo; dis[]=;vis[]=; head=;tail=;q[++tail]=; for(;head<=tail;head++){ int node=q[head]; for(int i=LINK[node];i;i=e[i].next) if(dis[e[i].y]>dis[node]+e[i].v){ dis[e[i].y]=dis[node]+e[i].v; if(!vis[e[i].y]){ if(cnt[e[i].y]==N){ puts("-1"); exit(); } cnt[e[i].y]++; q[++tail]=e[i].y; vis[e[i].y]=; } } vis[node]=; } } void output(){ ; cout<<dis[N]<<endl; } } int main(){ //freopen(FILE".in","r",stdin); //freopen(FILE".out","w",stdout); //freopen("input.in","r",stdin); using namespace solution; init(); SPFA(); output(); ; }
COGS1117的更多相关文章
随机推荐
-
作死遇到的坑--view向下偏移
好大一个坑.--谈谈view偏移问题: 先上张图, 图中白色部分.上面的是从网上找的资源.将导航栏隐藏之后用collectionView加上去而实现的滑动标签功能.开始以为是代码中的问题.然后仔细推敲 ...
-
jQuery Ztree基本用法
1.首先在页面上有<ul/>标签 <ul id="tree" class="ztree"></ul> 2.定义ztree的配 ...
-
Python 发送邮件包含附件报表示例
之前需要用Python发送报表邮件,在网上找了下资料,基本上符合要求了. 相关的示例如下,懂python的人应该都知道. from email.mime.text import MIMEText fr ...
-
JS中 confirm()方法的使用?
confirm() 方法用于显示一个带有指定消息和 OK 及取消按钮的对话框. 如果用户点击确定按钮,则 confirm() 返回 true.如果点击取消按钮,则 confirm() 返回 false ...
-
一步一步学习Vue(六)
本篇继续介绍vue-router,我们需要要完成这样个demo:<分页显示文章列表>:这里我们以博客园首页列表为例简化处理: 按照上图框选所示,简单分为蓝色部分文章组件(ArticleIt ...
-
团队作业9——展示博客(Bata版本)
1.团队成员介绍及项目地址 团队的源码仓库地址:https://coding.net/u/app24dian/p/app24dian/git 陈麟凤:(http://www.cnblogs.com/c ...
-
RNA-seq标准化
你的 heatmap 可能用错数据了 (组间表达量标准化) http://www.genek.tv/article/24 RNA-seq的标准化方法罗列 https://www.jianshu.com ...
-
android 开发 对话框Dialog详解
转载请注明出处:红亮的专栏:http://blog.csdn.net/liang5630/article/details/44098899 Android中的对话框形式大致可分为五种:分别是一般对话框 ...
-
sqlserver -- 查看当前数据库的数据表(备忘)
@_@||... 记性不好,备忘... 语句功能:查看当前数据库的所有表(根据所需,进行语句改写即可) SELECT * FROM sysobjects WHERE (xtype = 'U') 备注: ...
-
机器学习与R语言:C5.0
#---------------------------------------- # 功能描述:演示C50建模过程 # 数据集:汉堡大学信贷模型,信贷数据 # #------------------ ...