P4878 [USACO05DEC]Layout G+P2294 [HNOI2005]狡猾的商人

P2294 [HNOI2005]狡猾的商人

分不清就多跑几轮，没必要去纠结n次还是n+1次松弛。 话说bellman-ford每个点被松弛n-1次

		num[v]++;
        if(num[v]>n)
       {
         return 0;
       }

#include 

using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int n,m,head[maxn],cnt,dist[maxn],num[maxn];
bool vis[maxn];
struct node
{
    int to,nxt,dis;
}e[maxn];
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].dis=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
bool spfa(int u)
{
    queueq;
    memset(num,0,sizeof(num));
    memset(vis,0,sizeof(vis));
    memset(dist,inf,sizeof(dist));
    dist[u]=0;
    q.push(u);
    vis[u]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(dist[v]>dist[u]+e[i].dis)
            {
                dist[v]=dist[u]+e[i].dis;
                num[v]++;
                if(num[v]>n)
                {
                    return 0;
                }
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return 1;
}
signed main()
{
    int t;cin>>t;
    while(t--)
  {
    memset(head,0,sizeof(head));
    cnt=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i