CODE[VS]4416 FFF団潜伏の後宮

テーマ説明Description
あなたはある日FFF団の潜伏者の助けを得て、彼のある日旅行して帰ってきて、彼の後宮たちはいくつか調和のとれない矛盾が現れて、もしFFF団の潜伏者が自分の宝物をa番の妹に分けて、それではb番の妹は少なくともa番の妹の右側の距離dに立って、妹はやっとその宝物を手に入れたいです.しかし、后宫にも游び上手な女の子がいます.彼女たちはいつも亲しみを望んでいます.もし自分の宝物をa番の女の子に分けたら、彼女と亲しい女の子とa番の女の子の距离はlを超えません.今では全部でn人の妹がいて、k人のこのような矛盾関係、m人の親しい関係があります.もし彼の宝物が無限であると仮定して、すべての妹に宝物があることを保証する場合、n番目の妹と最初の妹の最も遠い距離はいくらですか?
入力記述Input Description
第1の挙動n,m,k
その後m行為親近関係
その後k行為矛盾関係
出力記述Output Description
1行、最長距離
サンプル入力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の範囲内
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
差分拘束～
問題はa−b>=xとa−b<=xの一連の関係に相当し,差分拘束解でよいことを見出した.
CODE[VS]freopenキーワードを禁止するなんて・・・私は口ずさむ.

#include
#include
#include
#include
#include 
using namespace std;

int n,m,k,x,y,z,fi[1001],w[10001],ne[10001],v[10001],cnt,dis[1001],inf,vis[1001];
bool b[1001];

queue q;

int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

void add(int u,int vv,int val)
{
	w[++cnt]=vv;ne[cnt]=fi[u];fi[u]=cnt;v[cnt]=val;
}

void spfa()
{
	memset(dis,127/3,sizeof(dis));
	inf=dis[0];dis[1]=0;q.push(1);
	while(!q.empty())
	{
		int k=q.front();q.pop();b[k]=0;
		for(int i=fi[k];i;i=ne[i])
		  if(dis[w[i]]>dis[k]+v[i])
		  {
		  	dis[w[i]]=dis[k]+v[i];
		  	vis[w[i]]++;
		  	if(vis[w[i]]>n)
		  	{
		  		dis[n]=-1;return;
		  	}
		  	if(!b[w[i]])
		  	{
		  		b[w[i]]=1;q.push(w[i]);
		  	}
		  }
	}
}

int main()
{
	n=read();m=read();k=read();
	for(int i=1;i<=m;i++) x=read(),y=read(),z=read(),add(x,y,z);
	for(int i=1;i<=k;i++) x=read(),y=read(),z=read(),add(y,x,-z);
	spfa();
	dis[n]=dis[n]==inf ? -2:dis[n];
	printf("%d
",dis[n]);
	return 0;
}