bool bellman_ford(int s){

    queue<int > Q;

    memset(inq,0,sizeof(inq));

    memset(cnt,0,sizeof(cnt));

    for(int i=0;i<n;i++) d[i]=INF;///初始化

    d[s]=0;///起点设为0

    inq[s]=true;///在队列中

    Q.push(s);

    while(!Q.empty()) {

        int u=Q.front();Q.pop();

        inq[u]=false;

        for(int i=0;i<G[u].size(); i++){///查找与u相连的边

            Edge& e=edges[G[u][i]];///取相连边

            if(d[u]<INF&&d[e.to]>d[u]+e.dist){///若u是路径中的边且到i的路径比原路径权值小，则加入路径

                d[e.to]=d[u]+e.dist;

                p[e.to]=G[u][i];///设置前驱边

                if(!inq[e.to]){///若新边不在路径中，加入队列

                    Q.push(e.to);

                    inq[e.to]=true;

                    if(++cnt[e.to]>n) return false;///有负圈

                }

            }

        }

    }

    return true;

}