题目描述 Description
你在某日收到了 FFF 团卧底的求助,在他某日旅游回来,他的后宫们出现了一些不可调和的矛盾,如果 FFF 团卧底把自己的宝贝分给 a 号妹子,那么 b 号妹子至少要在站在 a 号妹子的右边距离 d,妹子才愿意得到那个宝贝。可是后宫里也有玩得好的妹子呀,她们总是渴望亲近一点,如果把自己的宝贝分给 a 号妹子,那么与她亲近的妹子与 a 号妹子的距离不会超过 l。现在总共有 n 个妹子,k 个这样的矛盾关系,m 个亲近关系。假设他的宝贝是无限的,保证每一个妹子都有宝贝的情况下,第 n 个妹子和第一个妹子的最远距离是多少呢?
输入描述 Input Description
第一行为 n,m,k
此后 m 行为亲近关系
此后 k 行为矛盾关系
输出描述 Output Description
一行,为最长的距离
样例输入 Sample Input
4 2 1
1 3 100
2 4 200
2 3 33
样例输出 Sample Output
267
数据范围及提示 Data Size & Hint
对于 40%的数据,n<=100
对于 100%的数据,n<=1000,m<=10000,从 1 开始编号,距离在 int 范围内
图论 差分约束
差分约束模板题。
好像……没读懂题？描述不清是出题人的错吧！
前m个关系是给定 a,b,w，限制 b - a <=w
后k个关系是给定 a,b,w，限制 b-a>=w
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct edge{
int v,nxt,w;
}e[mxn<<];
int hd[mxn],mct=;
void add_edge(int u,int v,int w){
e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return;
}
int dis[mxn];
bool inq[mxn];
int vis[mxn];
queue<int>q;
int n,m1,m2;
void SPFA(){
memset(dis,0x3f,*(n+));
dis[]=;
q.push();
while(!q.empty()){
int u=q.front();q.pop();inq[u]=;
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
++vis[v];
if(vis[v]>n){printf("-1\n");exit();}
if(!inq[v]){ inq[v]=; q.push(v); }
}
}
}
return;
}
int main(){
int i,j,u,v,w;
n=read();m1=read();m2=read();
for(i=;i<=m1;i++){
u=read();v=read();w=read();
add_edge(u,v,w);
}
for(i=;i<=m2;i++){
u=read();v=read();w=read();
add_edge(v,u,-w);
}
SPFA();
if(dis[n]==0x3f3f3f3f)printf("-2\n");
else printf("%d\n",dis[n]);
return ;
}