题面lalala

这居然是个紫题???原谅我觉得这题是模板。。。

这个这个,这题的算法呢其实是一个叫差分约束的东西,也是今天下午我们机房的重点,如果不知道这个差分约束是个啥的人呢,自行百度一下谢谢。。

好吧还是简单介绍一下,简而言之,就是对一堆子不等式进行最短路模型化,然后依照问题用最短(长)路跑一(两)遍,基本上就可以求出答案

那么剩下的东西呢都在代码里了

 // luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std; int n,l,d,tot;
bool ok;
int dis[],c[],head[],next[],w[],to[];
bool vis[];
queue < int > q; void add(int v,int u,int p){//链式前向星不用多介绍了吧(这玩意要是不会的真的建议理解一下,平时做题复制粘贴虽然可以,但考场不行啊)
next[++tot]=head[v];
to[tot]=u;
w[tot]=p;
head[v]=tot;
} void spfa(int s){//由于可能有环及负权边,故用spfa求解
memset(dis,0x3f,sizeof(dis));
dis[s]=;
memset(c,,sizeof(c));
memset(vis,,sizeof(vis));
while(!q.empty()){q.pop();}
q.push(s);
vis[s]=;
ok=;
while(!q.empty()){
int x;
x=q.front();
q.pop();
vis[x]=;
for(int k=head[x];k;k=next[k]){
int y=to[k];
if(dis[x]+w[k]<dis[y]){
dis[y]=dis[x]+w[k];
if(!vis[y]){
vis[y]=;
c[y]++;
q.push(y);
}
if(c[y]>n){//处理负环的情况
ok=;
return;
}
}
}
}
return;
} int main(){
scanf("%d%d%d",&n,&l,&d);
for(int i=;i<=n;i++){//这段赋值可以对建图进行预处理,进而处理图非连通的情况
add(,i,);
}
for(int i=;i<=l;i++){//这个读入和下一个读入就是差分约束的核心,简而言之,就是小于等于时建一条a指向b权值为c的边(换行嘤嘤嘤)
int a,b,c;//大于等于时建一条b指向a权值为-c的边
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
for(int i=;i<=d;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(b,a,-c);
}
spfa();
if(!ok){//负环
printf("-1\n");
return ;
}
spfa();
if(!ok){//负环
printf("-1\n");
}
else if(dis[n]==0x3f3f3f3f){//不连通
printf("-2\n");
}
else{
printf("%d\n",dis[n]);//输出
}
return ;
}

嗯呐还有好多篇要写,就这样了

最新文章

  1. SQL Server-5种常见的约束
  2. MySQL 使用JOIN优化子查询
  3. Win10---------专区
  4. BZOJ2555——SubString
  5. PopupWindow
  6. 多线程BackgroundWorker
  7. Java对象克隆(Clone)及Cloneable接口、Serializable接口的深入探讨
  8. Report_客制化报表输出Excel后去0问题(案例)
  9. ffmpeg/ffplay vc6 源码剖析
  10. 显示 png 图片
  11. 【HDOJ】2510 符号三角形
  12. 捉Bug:易车注册页布局小臭虫 附demo
  13. T-SQL 语句
  14. SSM与jsp传递实体类
  15. docker学习笔记(一)—— ubuntu16.04下安装docker
  16. Python3.5 学习二十一
  17. Visual Studio 2017 系统发布部署服务器教程
  18. 第二阶段Sprint冲刺会议5
  19. matlab for 运算的提速
  20. hibernate cascade的真正含义

热门文章

  1. 10.17小作业 基于TCP开发一款远程CMD程序
  2. qt5-Qt Creator使用
  3. 2017noip总结
  4. SQLSERVER 连接常见问题
  5. BZOJ 1095: [ZJOI2007]Hide 捉迷藏 动态点分治+堆
  6. 51 Nod 大鱼吃小鱼
  7. java取小数点后两位
  8. 前端MVC、MVVM的简单实现
  9. Javascript事件:this.value()和this.select()
  10. LeetCode 236. 二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree)