/*
SPFA(Shortest Path Faster Algorithm) [图的存储方式为邻接表]
是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，
并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
SPFA 在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中
一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本
身被改进，于是再次用来改进其它的点，这样反复迭代下去。
判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。
SPFA算法有两个优化算法 SLF 和 LLL：
SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，
否则插入队尾。
LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入
到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。
引用网上资料，SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。
在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。
*/
 
//用数组实现邻接表存储，pnt[i,0]表示与i相邻的结点个数，pnt[i,1...k]存储与i相邻的点

int SPFA(){
    for(int i = 1; i <= n; i++){
        head[i] = 0;	
        dst[i] = INF;
        vis[i] = false;
        slack[i] = 0;
    }
	while(que.empty() == false)que.pop();
	que.push(1);
	dst[1] = 0;
	vis[1] = true;
	while(que.empty() == false){
		int idx = que.front();que.pop();
		vis[idx] = false;
		for(int i = head[idx]; i != 0; i = e[i].nxt){
			int to = e[i].to;
			int d = dst[idx] + e[i].w;
			if(d < dst[to]){
				dst[to] = d;
				slack[to] = slack[idx] + 1;
				if(slack[to] >= n){
					printf("YES\n");
					return 1;
				}
				
				if(vis[to])continue;
				vis[to] = true;
				que.push(to);
			}
		}
	}
	printf("NO\n");
	return 0;
}

void floyd(int idx){
	for(int k = 0; k < n; k++)
	for(int i = 0; i <n; i++){
		for(int j = i + 1; j < n; j++){
			adj[j][i] = adj[i][j] = min(adj[i][idx] + adj[idx][j], adj[i][j]);
		}
	}
}