這道題是一個農場有F個神奇的農場
農場有N個點,M條路,W個蟲洞。蟲洞能回溯時間。
問能不能從某個點出發,通過路和蟲洞,回到原點,時間比原來早。
我第一思路是用bellman-ford算法,可以求是否出現負權值情況來做。
提交了好幾次不對,發現坑爹之處是M條路是雙向的,W個蟲洞是單向的,理解了這個以後就能做了。它是要求某個點,所以要便利所有點來做bellman算法。
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int from,to,cost;
edge(int f,int t,int c):from(f),to(t),cost(c){};
edge(){}
};
edge es[3000];
int d[550];
int F,N,M,W;
void bellman(){
for (int k = 1; k <= N; ++k)
{
memset(d,INF,sizeof(d));
d[k]=0;
int flag=1;
while(flag){
flag=0;
for (int i = 0; i < M+W; ++i)
{
edge e=es[i];
if (d[e.from]!=INF&&d[e.from]+e.cost=0)
{
d[e.to]=d[e.from]+e.cost;
flag=1;
}
if (i=0)
{
d[e.from]=d[e.to]+e.cost;
flag=1;
}
}
}
if (d[k]<0){
printf("YES\n");
return ;
}
}
printf("NO\n");
}
int main(int argc, char const *argv[])
{
scanf("%d",&F);
int x,y,w;
while(F--){
scanf("%d%d%d",&N,&M,&W);
int i;
for ( i = 0; i < M; ++i)
{
scanf("%d%d%d",&x,&y,&w);
es[i].from=x;
es[i].to=y;
es[i].cost=w;
}
for (; i