在做 $johnson$ 最短路问题时遇到一个问题，同样的代码，修改一句就可以比原来快一倍。

代码如下，分为$spfa$ 函数、 $dijkstra$ 函数、 主函数三块，在 $dijkstra$ 函数的开头，如果队列元素为 $pair$ ，总时长在2.3s左右；如果队列元素为 $node$ ，总时长在1.2s左右。

我的问题是：1.这里的 $pair$ 和 $node$ ，同样都是包含两个整数，为什么速度差距这么大？是构造的慢，还是移动得慢，还是什么原理？我猜想过在 $pair.first$ 打平的情况下会继续比较 $pair.second$ ，这个会耗时。但是我重载了这个比较函数，$pair$ 加快了一些，但是只能到1.6-1.7s。2.在一般情况下，推荐使用结构体还是 $pair/tuple$ ?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF=1000000000;
template <class T>bool chmin(T& a, const T& b){if (b < a){a = b;return 1;}else return 0;}
int _IO=[](){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
return 0;}();

int n,m,first[3000],nxt[12000],from[12000],to[12000],cost[12000],h[3000],t[3000];
bool spfa(){
    queue<int>q;
    vector<bool>inq(n,false);
    for(int i=0;i<n;i++)h[i]=0,q.push(i),inq[i]=true;
    while(q.size()){
        int p=q.front();q.pop();inq[p]=false;
        for(int cur=first[p];~cur;cur=nxt[cur]){
            int _to=to[cur],_cost=cost[cur];
            if(chmin(h[_to],h[p]+_cost) and !inq[_to]){
                q.push(_to),inq[_to]=true,t[_to]++;
                if(t[_to]>n)return false;
            }
        }
    }
    return true;
}

struct node{
    int dis, id;
    bool operator<(const node& a) const { return dis > a.dis; }
    node(int d, int x) { dis = d, id = x; }
};
int dis[3000];
void dijkstra(int i){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>Q;
    // priority_queue<node>Q;
    fill(dis, dis+n, INF);
    dis[i]=0, Q.emplace(dis[i], i);
    while(Q.size()){
        auto [curd,p] = Q.top(); Q.pop();
        if(curd==dis[p]){
            for(int cur=first[p];~cur;cur=nxt[cur]){
                int _to=to[cur], _cost=cost[cur];
                if(chmin(dis[_to],curd+_cost))
                    Q.emplace(dis[_to],_to);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    fill(first,first+n,-1);
    for(int i=0;i<m;i++){
        cin>>from[i]>>to[i]>>cost[i];
        from[i]--,to[i]--;
        nxt[i]=first[from[i]],first[from[i]]=i;
    }
    if(!spfa())cout<<-1;
    else{
        for(int i=0;i<m;i++)cost[i]+=h[from[i]]-h[to[i]];
        for(int i=0;i<n;i++){
            dijkstra(i);
            ll sum=0,j;
            for(j=0;j<n;j++)sum+=dis[j]==INF?(j+1)*dis[j]:(j+1)*(dis[j]+h[j]-h[i]);
            cout<<sum<<'\n';
        }
    }
}