/*

    SPFA模板

 */

 const int inf=0x3f3f3f3f;

 inline int SPFA(int s){

     memset(dis,inf,sizeof(dis));

     queue<int > q;

     dis[s]=;

     q.push(s);

     vis[s]=;

     while(!q.empty()){

         int u=q.front;

         q.pop();

         vis[u]=;

         for(int i=head[u];i;i=edge[i].next ){

             int v=edge[i].to ;

             if(dis[v]>dis[u]+edge[i].value ){

                 dis[v]=dis[u]+edge[i].value ;

                 if(!vis[v]){

                     vis[v]=;

                     q.push(v);

                 }

                 cntt[v]++;

                 if(cntt[v]>=n) return ;

             }

         }

     }

     return ;

 } 

/*

    dijstra模板 (堆优化)

*/

const int inf=0x3f3f3f3f;

typedef pair<int ,int > p

inline void dijstra(int s){

    memset(dis,inf,sizeof(dis))

    priority_queue<p,vector<p>,greater<p> > q;

    dis[s]=;

    q.push(make_pair(,s));//pair类型默认先比较第一项

    while(!q.empty()){

        int u=q.top().second;

        int w=q.top().first;

        q.pop();

        if(dis[u]!=w) continue;

        for(int i=head[u];i;i=edge[i].next ){

            int v=edge[i].to ;

            if(dis[v]>dis[u]+edge[i].value ){

                dis[v]=dis[u]+edge[i].value ;

                q.push(make_pair(dis[v],v));

            }

        }

    }

} 

 /*

     floyd模板

 */

 inline void floyd(){

     for(int k=;k<=n;k++)

      for(int i=;i<=n;i++)

       for(int j=;j<=n;j++){

           dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);

         //或者：

         if(dis[i][j]>dis[i][k]+dis[k][j])

           dis[i][j]=dis[i][k]+dis[k][j];

       }

 }