时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi的学校总共有N名学生,编号1-N。学校刚刚进行了一场全校的古诗文水平测验。

学校没有公布测验的成绩,所以小Hi只能得到一些小道消息,例如X号同学的分数比Y号同学的分数高S分。

小Hi想知道利用这些消息,能不能判断出某两位同学之间的分数高低?

输入

第一行包含三个整数N, M和Q。N表示学生总数,M表示小Hi知道消息的总数,Q表示小Hi想询问的数量。

以下M行每行三个整数,X, Y和S。表示X号同学的分数比Y号同学的分数高S分。

以下Q行每行两个整数,X和Y。表示小Hi想知道X号同学的分数比Y号同学的分数高几分。

对于50%的数据,1 <= N, M, Q <= 1000

对于100%的数据,1 <= N, M, Q<= 100000 1 <= X, Y <= N -1000 <= S <= 1000

数据保证没有矛盾。

输出

对于每个询问,如果不能判断出X比Y高几分输出-1。否则输出X比Y高的分数。

样例输入
10 5 3
1 2 10
2 3 10
4 5 -10
5 6 -10
2 5 10
1 10
1 5
3 5
样例输出
-1
20
0

开始以为是存在环(矛盾的分数),这样的话,可能要判环。读完题发现没有矛盾存在,这样的话并查集+bfs乱搞

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<memory>
using namespace std;
const int maxn=;
int Laxt[maxn],Next[maxn],To[maxn],V[maxn],cnt=;
int fa[maxn],scr[maxn];//fa是分组,score代表相对分数。
void _add(int u,int v,int s){
Next[++cnt]=Laxt[u];
Laxt[u]=cnt;
To[cnt]=v;
V[cnt]=s;
}
void _dfs(int u){
for(int i=Laxt[u];i;i=Next[i]){
if(!fa[To[i]]){
fa[To[i]]=fa[u];
scr[To[i]]=scr[u]-V[i];
_dfs(To[i]);
}
}
}
int main()
{
int n,m,q,i,x,y,s;
scanf("%d%d%d",&n,&m,&q);
for(i=;i<=m;i++){
scanf("%d%d%d",&x,&y,&s);
_add(x,y,s);
_add(y,x,-s);
}
for(i=;i<=n;i++)
if(!fa[i]){
fa[i]=i;
_dfs(i);
}
for(i=;i<=q;i++){
scanf("%d%d",&x,&y);
if(fa[x]!=fa[y]) printf("-1\n");
else printf("%d\n",scr[x]-scr[y]);
}
return ;
}

最新文章

  1. 不从SD卡启动树莓派2
  2. 让UserControl能显示焦点状态
  3. ODAC(V9.5.15) 学习笔记(十八) 数据集缓冲模式
  4. Effective Java 45 Minimize the scope of local variables
  5. python 读写文件和设置文件的字符编码
  6. ios uitableviewcell动态计算高度
  7. 晒下自己App广告平台积分墙收入,顺便点评几个广告平台
  8. VPN怎么连?
  9. 二、JSP的3个编译指令,7个动作指令,9个内置对象
  10. [unity菜鸟] 修改发布成web后的logo
  11. Debugging to Understand Finalizer--reference
  12. 从一个PHP数据生成 CSV 文件
  13. DICOM医学图像处理:DCMTK在VS2012中的配置
  14. DDOS学习笔记(《破坏之王-DDOS攻击与防范深度剖析》)
  15. thinkphp3.2.3使用ajax 的一些坑——使用AjaxReturn()后,直接返回null,模板文件不起作用
  16. 第5章 简单的C程序设计——循环结构程序设计
  17. 【BZOJ5492】[HNOI2019]校园旅行(bfs)
  18. Linux第一节课学习笔记
  19. bzoj4556(sam)
  20. Html5游戏框架createJs组件--EaselJS(二)绘图类graphics

热门文章

  1. gdb 调试coredump文件过程:
  2. codeforces570D Tree Requests
  3. HttpGet/HttpPost请求方法
  4. pg_ctl -- 启动、停止、重启 PostgreSQL
  5. Java 最常见的 200+ 面试题:面试必备
  6. 负载均衡,会话保持,session同步
  7. macOS和常用命令
  8. C#/JAVA 程序员转GO/GOLANG程序员笔记大全(DAY 02)
  9. SSH集成log4j日志环境
  10. 009PHP基础知识——运算符(二) 逻辑运算符