COGS1117

时间:2022-09-03 08:52:13

传送门:

差分约束第一题。

所有的条件无非两种不等式

$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的更多相关文章

    随机推荐

    1. 作死遇到的坑--view向下偏移

      好大一个坑.--谈谈view偏移问题: 先上张图, 图中白色部分.上面的是从网上找的资源.将导航栏隐藏之后用collectionView加上去而实现的滑动标签功能.开始以为是代码中的问题.然后仔细推敲 ...

    2. jQuery Ztree基本用法

      1.首先在页面上有<ul/>标签 <ul id="tree" class="ztree"></ul> 2.定义ztree的配 ...

    3. Python 发送邮件包含附件报表示例

      之前需要用Python发送报表邮件,在网上找了下资料,基本上符合要求了. 相关的示例如下,懂python的人应该都知道. from email.mime.text import MIMEText fr ...

    4. JS中 confirm&lpar;&rpar;方法的使用?

      confirm() 方法用于显示一个带有指定消息和 OK 及取消按钮的对话框. 如果用户点击确定按钮,则 confirm() 返回 true.如果点击取消按钮,则 confirm() 返回 false ...

    5. 一步一步学习Vue(六)

      本篇继续介绍vue-router,我们需要要完成这样个demo:<分页显示文章列表>:这里我们以博客园首页列表为例简化处理: 按照上图框选所示,简单分为蓝色部分文章组件(ArticleIt ...

    6. 团队作业9——展示博客(Bata版本)

      1.团队成员介绍及项目地址 团队的源码仓库地址:https://coding.net/u/app24dian/p/app24dian/git 陈麟凤:(http://www.cnblogs.com/c ...

    7. RNA-seq标准化

      你的 heatmap 可能用错数据了 (组间表达量标准化) http://www.genek.tv/article/24 RNA-seq的标准化方法罗列 https://www.jianshu.com ...

    8. android 开发 对话框Dialog详解

      转载请注明出处:红亮的专栏:http://blog.csdn.net/liang5630/article/details/44098899 Android中的对话框形式大致可分为五种:分别是一般对话框 ...

    9. sqlserver -- 查看当前数据库的数据表(备忘)

      @_@||... 记性不好,备忘... 语句功能:查看当前数据库的所有表(根据所需,进行语句改写即可) SELECT * FROM sysobjects WHERE (xtype = 'U') 备注: ...

    10. 机器学习与R语言:C5&period;0

      #---------------------------------------- # 功能描述:演示C50建模过程 # 数据集:汉堡大学信贷模型,信贷数据 # #------------------ ...

    相关文章