題意：John的農場裡field塊地，path條路連接兩塊地，hole個蟲洞，蟲洞是一條單向路，不但會把你傳送到目的地，而且時間會倒退Ts。我們的任務是知道會不會在從某塊地出發後又回來，看到了離開之前的自己。
思路：用bellman-ford 判斷有沒有負權回路，如果有他就能看到自己。 不過，我認為應該判斷每個點有沒有負權回路，而不僅僅只判斷第一個點就行了。
AC代碼
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int VM=520;
const int EM=2600;
const int INF=0x3f3f3f3f;
struct Edge{
int u,v;
int cap;
}edge[EM<<1];
int n,m,k;
int cnt,dis[VM];
int Bellman()
{
int i,j;
for(i=1;i<=n;i++)
{
dis[i]=INF;
}
dis[1]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=cnt-1;j++)
{
if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cap)
{
dis[edge[j].v]=dis[edge[j].u]+edge[j].cap;
}
}
}
for(j=1;j<cnt-1;j++)
{
if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cap)
{
return 0;
}
}
return 1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
cnt=1;
int u,v,w;
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt++].cap=w;
edge[cnt].u=v;
edge[cnt].v=u;
edge[cnt++].cap=w;
}
while(k--)
{
scanf("%d%d%d",&u,&v,&w);
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt++].cap=-w;
}
int ans=Bellman();
if(ans==0){
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int VM=520;
const int EM=2600;
const int INF=0x3f3f3f3f;
struct Edge{
int u,v;
int cap;
}edge[EM<<1];
int n,m,k;
int cnt,dis[VM];
int Bellman()
{
int i,j;
for(i=1;i<=n;i++)
{
dis[i]=INF;
}
dis[1]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=cnt-1;j++)
{
if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cap)
{
dis[edge[j].v]=dis[edge[j].u]+edge[j].cap;
}
}
}
for(j=1;j<cnt-1;j++)
{
if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cap)
{
return 0;
}
}
return 1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
cnt=1;
int u,v,w;
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt++].cap=w;
edge[cnt].u=v;
edge[cnt].v=u;
edge[cnt++].cap=w;
}
while(k--)
{
scanf("%d%d%d",&u,&v,&w);
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt++].cap=-w;
}
int ans=Bellman();
if(ans==0){
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
