誒，真的是越活越回去了，現在打的程序還不如以前了，慢的爆炸……（先測的是bellman-ford，后測的是SPFA）

題目大意：FJ想要進行時光旅行，現在有F個農場，對于每個農場，已知該農場有N片農田，M條小路，W個蟲洞。其中小路是雙向的，蟲洞是單向的。對于每條小路，有S,E,T三個參數：S和E表示小咯兩端農田的序號，通過這條小咯需要的T的時間。對于每個蟲洞，同樣有S,E,T三個參數：S表示蟲洞起點所在的農田的序號，E表示蟲洞終點所在的農田的序號，通過這個蟲洞需要-T的時間。現在FJ想知道他在每個農場是否能回到從前。

我們從題目中可以清晰的看出，題目就是想讓我們求每個農場是否存在負權環。一道大水題。

方法一：bellman-ford，用side數組來存邊。若松弛次數超過n次，就說明存在負權環。

#include <cstdio>#include <vector>#include <cstring>using namespace std;struct note{	int x,y,w;}side[2710];int ti,n,m,p,x,y,w,dis[510],g;bool b;int main(void){	scanf("%d",&ti);	while (ti--){		scanf("%d%d%d",&n,&m,&p);		for (int i=1; i<=m; ++i)			scanf("%d%d%d",&side[i].x,&side[i].y,&side[i].w);		for (int i=m+1; i<=m+p; ++i)			scanf("%d%d%d",&side[i].x,&side[i].y,&side[i].w),side[i].w*=-1;		memset(dis,0x3f,sizeof(dis));		b=1,g=0;dis[1]=0;		while (b){			b=0;			if (++g>n) break;			for (int i=1; i<=m; ++i){				if (dis[side[i].y]>dis[side[i].x]+side[i].w)					dis[side[i].y]=dis[side[i].x]+side[i].w,b=1;				if (dis[side[i].x]>dis[side[i].y]+side[i].w)					dis[side[i].x]=dis[side[i].y]+side[i].w,b=1;			}			for (int i=m+1; i<=m+p; ++i)			if (dis[side[i].y]>dis[side[i].x]+side[i].w)					dis[side[i].y]=dis[side[i].x]+side[i].w,b=1;		}		if (g>n) PRintf("YES/n");			else printf("NO/n");	}	return 0;}方法二：SPFA——bellman-Ford的隊列優化升級版，可惜在這題中慢的起飛……（好像是因為SPFA計算了許多不必要的路線）若一個節點入隊超過n次就說明存在負權環。
#include <cstdio>#include <cstring>#include <queue>using namespace std;queue <int> que;int t,n,m1,m2,x,y,w,map[510][510],c[510],dis[510];bool b,bo[510];bool spfa(int s){	while (!que.empty()) que.pop();	memset(c,0,sizeof c);	memset(bo,0,sizeof bo);	memset(dis,0x3f,sizeof dis);	que.push(s);c[s]=1;bo[s]=1;	while (!que.empty()){		int p=que.front();que.pop();		bo[p]=0;		for (int i=1; i<=n; ++i)			if (dis[i]>dis[p]+map[p][i]){				dis[i]=dis[p]+map[p][i];				if (!bo[i]){					if (++c[i]>n) return 1;					bo[i]=1;					que.push(i);				}			}	}	return 0;}int main(void){	scanf("%d",&t);	while (t--){		scanf("%d%d%d",&n,&m1,&m2);		memset(map,0x3f,sizeof map);		for (int i=1; i<=m1; ++i){			scanf("%d%d%d",&x,&y,&w);			if (w<map[x][y]) map[x][y]=map[y][x]=w;		}		for (int i=1; i<=m2; ++i){			scanf("%d%d%d",&x,&y,&w);			map[x][y]=-w;		}		b=0;		for (int i=1; i<=n; ++i)			if (spfa(i)){				b=1;				break;			}		if (b) printf("YES/n");			else printf("NO/n");	}	return 0;}寫在最后：雖然SPFA的運行速度過慢可能跟計算了許多不必要的路線有關，但是和我用的是鄰接矩陣有不可分割的關系。在以后的做題過程中，盡量用高級一些的數據結構，獅子搏兔亦用全力。