Ryan_<

首先题目中的隐含条件是

d[i] <= d[i + 1] 

即d[i + 1] + 0 >= d[i]

 

然后对那ML个条件

d[y] - d[x] <= w -> d[x] + w >= d[y]

对那MD个条件

d[y] - d[x] >= w -> d[y] + (-w) >= d[x] 

 

然后呢就可以加边了。

对于一个不等式 d[u] + w >= d[v] 我们可以加边(u, v , w)

这是由于在一个图里，从s出发，到各个顶点的v最短距离为d[v]，那么对一个边(u, v, w) 必然有d[u] + w >= d[v]

 

我的代码：（18:05-18:32，1A）

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define inf 1<<30
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
using namespace std;
const int M=15000,N=1500;
struct edge{
	int go,next,w;
}e[M];
int n,s,ml,md,d[N],head[N],cnt[N],tot=0;
bool inq[N];
inline void addedge(int x,int y,int z)
{e[++tot]=(edge){y,head[x],z};head[x]=tot;}
#include<queue>
queue<int> q;
inline bool spfa()
{
	s=1;
	F(i,1,n) d[i]=inf;
	d[s]=0;
	memset(inq,false,sizeof(inq));
	memset(cnt,0,sizeof(cnt));
	q.push(s);
	inq[s]=true;
	while(!q.empty()){
		int x=q.front();q.pop();
		inq[x]=false;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].go;
			if(d[y]>d[x]+e[i].w){
				d[y]=d[x]+e[i].w;
				if(!inq[y]){
					q.push(y);
					inq[y]=true;
					if(++cnt[y]>n)
						return false;
				}
			}
		}
	}
	return true;
}
int main()
{
	int a,b,c;
	scanf("%d%d%d",&n,&ml,&md);
	F(i,1,n) addedge(i+1,i,0);
	F(i,1,ml){
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);//a->b 权值为c
	}
	F(i,1,md){
		scanf("%d%d%d",&a,&b,&c);
		addedge(b,a,-c);//b->a 权值为-c
  }
  spfa();
  if(!spfa()) puts("-1");
  else if(d[n]==inf) puts("-2");
  else printf("%d\n",d[n]);
  return 0;
}