//poj 3259
#include <iostream>
#include <queue>
#include "stdio.h"
#define inf 1000000000
using namespace std;
queue <int> q;
int f;
int n,m,w;
int s,e,t;
int map[510][510];
int dis[510];
int v[510];
int cnt[510];
bool spfa()
{
 	v[1]=1;
 	cnt[1]++;
	 q.push(1);
	 int temp;
	 dis[1]=0;
	
	 while(!q.empty())
	 {
	  				  temp=q.front();
	  				  q.pop();
	  				  v[temp]=0;
	  				  for(int i=1;i<=n;i++)
						{
						 	  if(i!=temp&&map[temp][i]<inf&&dis[i]-map[temp][i]>dis[temp])
							   {
							   						dis[i]=dis[temp]+map[temp][i];
													
													
														   if(v[i]==0){
														   			   v[i]=1;
														   			   cnt[i]++;
														   			   if(cnt[i]>=n)return true;
														   			   q.push(i);
																		  }
														 	   
							   }
		 	            }
     } 
     return false;
}

int main(){
	
	cin>>f;
	for(int k=0;k<f;k++)
	{
	 		
	 		while(!q.empty()){q.pop();}
	 		for(int i=0;i<510;i++)
	 		for(int j=0;j<510;j++)
	 		{if(i==j)map[i][j]=0;
	 		 else map[i][j]=inf;
		    }
	 	//	memset(dis,0,sizeof(dis));
	 		memset(v,0,sizeof(v));
	 		memset(cnt,0,sizeof(cnt));
	 		for(int j=1;j<=n;j++)dis[j]=inf;
			 cin>>n>>m>>w;
	 		for(int j=0;j<m;j++)
			 {
			  		
		            cin>>s>>e>>t;
			  		map[s][e]=t;
			  		map[e][s]=t;
  		     }
  		     for(int j=0;j<w;j++)
			   {
			   		 cin>>s>>e>>t;
			   		 map[s][e]=-t;
   		       }
            if(spfa())cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
	}
	
}

• Re:你根本不是500！还有重边 (305) 3009216068 2012-08-25 00:10:18