#include<iostream>

using namespace std;
#define Max 10002
int ta,tb,a[Max],b[Max],c[Max],sa[Max],sb[Max],sc[Max];
int d[1002];
int n,maxa,maxb;
void bellman()
{
	int k=0,i;
   bool used=false;
   memset(d,0,sizeof(d));
   d[n]=-1;
   while(!used)
   {
	   k++;
	   if(k>=n)
		   break;
	   used=true;
	   for(i=0;i<ta;i++)
	   {
		   if(d[b[i]]<d[a[i]])
			   d[b[i]]=d[a[i]],used=false;
		   if(d[b[i]]<d[a[i]]+c[i])
		   {
			   d[b[i]]=d[a[i]]+c[i];
			   used=false;
		   }
		 
	   }

		   for(i=0;i<tb;i++)
		   {
			   if(d[sb[i]]<d[sa[i]])
				   d[sa[i]]=d[sb[i]],used=false;
			   if(d[sb[i]]>d[sa[i]]+sc[i])
			   {
				   d[sa[i]]=d[sb[i]]-sc[i];
				   used=false;
			   }
			   
		   }

			 for(i=2;i<=n;i++)
				   if(d[i]<d[i-1])
				   {
					   used=false;
					   d[i]=d[i-1];
				   }


   }
   if(d[n]<0)
	   cout<<-2<<endl;
   else if(k>=n)
	   cout<<-1<<endl;
   else
	   cout<<d[n]-d[1]<<endl;
   

}
int main()
{
	int i;
	scanf("%d%d%d",&n,&ta,&tb);
	for(i=0;i<ta;i++)
	{
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		if(a[i]>b[i])
			swap(a[i],b[i]);
		//maxa=b[i]>maxa?b[i]:maxa;
	}
	for(i=0;i<tb;i++)
	{
		scanf("%d%d%d",&sa[i],&sb[i],&sc[i]);
		if(sa[i]>sb[i])
			swap(sa[i],sb[i]);
		//	maxb=b[i]>maxb?b[i]:maxb;
	}
   bellman();
	return 0;
}

• 很奇怪。。我们的程序几乎一样了 (1516) gaosimeng 2007-08-21 13:41:59
  • Re:很奇怪。。我们的程序几乎一样了 (9) star6 2007-08-21 13:48:43
• 没有看出是哪个地方错了 (1516) superman2006 2007-08-21 15:51:51
• Re:d从小的方向松弛为啥总是wa？？？？？ (23) justjude 2007-11-05 19:50:12