spfa求代负权边的最短路

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010,M = 200010;
int q[2 * M], hh = 0, tt = -1; //数组模拟队列
bool vis[N]; //判断是否已经在对立中
int dis[N];
int n, m;
int h[N], e[M], ne[M], w[M], idx;

void add(int a,int b, int wei) //添加一条有向边
{
    e[idx] = b, w[idx] = wei, ne[idx] = h[a], h[a] = idx++; //头插法构造链表
//  cout << idx << " " << wei;
}


void spfa() //距离当前最近的点才进行松弛
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0; //从第1个节点开始
    vis[1] = 1; 
    q[++tt] = 1; //第一个节点入对
    
    while(hh <= tt)
    {
        int ver = q[hh++]; //取头节点
        vis[ver]  = 0; //不在对列中，更新状态
        
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; //获取临界节点的 节点号
            if(dis[j] > dis[ver] + w[i]) //注意w要用idx号的嗷
            {
                dis[j] = dis[ver] + w[i];
//              cout << j << " " << dis[ver] << " " << w[j] << endl;
                if(!vis[j]) //当前节点被更新了，入队 + 状态更新
                { 
                    q[++tt] = j;
                    vis[j] = 1;
                }
            }
        }
        
        
    }
    
}

int main()
{   
    cin >> n >> m;
    //0.init
    memset(h, -1, sizeof h); //初始化头节点
    //1.I
    for(int i = 1; i <= m; i++)
    {
        int a, b, wei; scanf("%d%d%d", &a, &b, &wei);
        add(a, b, wei); //有向图只添加一次就好了
    }
    //2.P
    
    spfa();
    
    //3.O
//  for(int i = 1; i <= n; i++)
//      {
//          for(int j = 1;j <= n; j++)
//              printf("%d ", dis[i][j]);
//          puts(""); 
//      }   
    
    for(int i = 2; i <= n; i++)
        printf("%d\n", dis[i]);

//  printf("%d", g[1][n]);
}