poj 3259 Wormholes

Wormholes

题目链接：http://poj.org/PRoblem?id=3259

题目大意:主角通过平常路径还有虫洞，在某一点出发，能回到出发前的时刻，问是否存在这样的点；

本质：带有负权的路径，首选，弗洛伊德算法；

代码如下：

#include <iostream>  #include <cstdio>using namespace std;  const int INF=0x3f3f3f3f; int dis[505][505]; int main()  {      int n,m,p,q,s;    int t,w;    cin>>t;    int flag;    while(t--)    {    	flag=0;    	cin>>n>>m>>w;        for (int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                  dis[i][j]=INF;            }        }        for(int i=1;i<=n;i++)        	dis[i][i]=0;        for (int i=0;i<m;i++)          {              scanf("%d%d%d",&p,&q,&s);			if(s<dis[p][q])			   dis[p][q]=dis[q][p]=s;        }        for(int i=0;i<w;i++)        {        	scanf("%d%d%d",&p,&q,&s);                          if(-s<dis[p][q])				dis[p][q]=-s;		}        for (int k=1;k<=n;k++)         {        	if(flag)        		break;            for (int i=1;i<=n;i++)              {                  for (int j=1;j<=n;j++)                {                    if (dis[i][j]>dis[i][k]+dis[k][j])                    {                          dis[i][j]=dis[i][k]+dis[k][j];                     }                }                if(dis[i][i]<0)//没有这个if会超时				{					flag=1;					break;				}            }         }		if(flag)			printf("YES/n");		else			printf("NO/n");    }      return 0;  }