Dij

bool visit[MAXN];        priority_queue
     
      
       , vector
       
        
          >, greater
         
          
            > > que; pair
           
             cnt; memset(visit, false, sizeof(visit)); visit[st] = true; que.push(make_pair(0, st)); while (!que.empty()) { cnt = que.top(); que.pop(); int ucost = cnt.first; int u = cnt.second; for (int i = Head[u]; i; i = nxt[i]) { int v = to[i]; if (visit[v]) { continue; } visit[v] = true; if (dis[v] > dis[u] + cost[i]) { dis[v] = dis[u] + cost[i]; que.push(make_pair(dis[v], v)); } } }
           
          
         
        
       
      
     

SPFA

dfs求负环版

#include
      
       using namespace std;const int maxn = 2e5+ 5;struct lpl{ int to, dis; }lin;vector
       
         point[maxn];int n, m, dis[maxn];bool Flag, vis[maxn];inline void connect(int a, int b, int w){ lin.to = b; lin.dis = w; point[a].push_back(lin); }inline void putit(){    int a, b, w;    scanf("%d%d", &n, &m);    for(int i = 1; i <= n; ++i) point[i].clear();    for(int i = 1; i <= m; ++i)    {        scanf("%d%d%d", &a, &b, &w);        connect(a, b, w);        if(w > 0) connect(b, a, w);    }}void SPFA(int t){    int now; vis[t] = true;    for(int i = point[t].size() - 1; i >= 0; --i)    {        now = point[t][i].to;        if(dis[now] > dis[t] + point[t][i].dis)        {            dis[now] = dis[t] + point[t][i].dis;            if(vis[now] == true || Flag == true) { Flag = true; break; }            SPFA(now);        }    }    vis[t] = false;}int main(){    int T; scanf("%d", &T);    while(T--)    {        putit();        memset(dis, 0, sizeof(dis)); memset(vis, false, sizeof(vis)); Flag = false;        for(int i = 1; i <= n; ++i) { SPFA(i); if(Flag == true) break; }        if(Flag == true) { printf("YE5\n"); continue;}        printf("N0\n");    }    return 0;}
       
      

 

bool visit[MAXN];        queue
     
       que;        memset(visit, false, sizeof(visit));        dis[st] = 0, visit[st] = true;        que.push(st);        while (!que.empty())        {                int u = que.front();                que.pop();                visit[u] = false;                for (int i = Head[u]; i; i = nxt[i])                {                        int v = to[i];                        if (dis[v] > dis[u] + cost[i])                        {                                dis[v] = dis[u] + cost[i];                                if (!visit[v])                                {                                        visit[v] = true;                                        que.push(v);                                }                        }                }        }