题解 p1828 【香甜的黄油 sweet butter】

本蒟蒻看楼上一群大佬用STL写SPFA，就想着用普通的SPFA写一篇题解。
看题目也知道，如果只是朴素的FLOYED肯定是会超时的，所以这里考虑使用最快的SPFA算法。
话不多说，上代码~~

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std；
int n,p,c,i,j,x,y,t,min1,head,tail,tot,u;
inta[801][801],b[501],dis[801],num[801],w[801][801],team[1601];
bool exist[801];
int main()
{
    cin>>n>>p>>c;
    for(i=1;i<=p;i++)
        for(j=1;j<=p;j++)
            w[i][j]=0x7fffffff/3;  
    for(i=1;i<=n;i++)
        cin>>b[i];
    for(i=1;i<=c;i++)     //邻接矩阵存储
    {
        cin>>x>>y>>t;
        w[x][y]=w[y][x]=t;  //双向
        a[x][++num[x]]=y;   //存储于每个牧场相连的牧场序号
        a[y][++num[y]]=x;
    }
    min1=0x7fffffff/3;
    for(i=1;i<=p;i++)
    {
        for(j=1;j<=p;j++) dis[j]=0x7fffffff/3;memset(team,0,sizeof(team)); //队列数组初始化memset(exist,false,sizeof(exist)); //标记数组初始化
dis[i]=0;team[1]=i;head=0;tail=1;exist[i]=true; //起始点入队
        do
        {
            head++;
            head=((head-1)%1601)+1;   //循环队列，有效节约空间
            u=team[head];
            exist[u]=false;
            for(j=1;j<=num[u];j++)//循环判断每一个与头相连的点
                if(dis[a[u][j]]>dis[u]+w[u][a[u][j]])
                {
                    dis[a[u][j]]=dis[u]+w[u][a[u][j]];
                    if(!exist[a[u][j]])  //入队操作
                    {
                        tail++;
                        tail=((tail-1)%1601)+1;
                        team[tail]=a[u][j];
                        exist[a[u][j]]=true;
                    }
                }
        }while(head!=tail);
        tot=0;
        for(j=1;j<=n;j++)
        tot+=dis[b[j]];
        if(tot<min1) min1=tot;
    }
    cout<<min1;
    return 0;
}