题解 P1828 【香甜的黄油 Sweet Butter】

「QQ红包」 · 2016-08-09 17:21:26 · 题解

SPFA模板题。枚举放置糖果的位置。

/*
ID: ylx14274
PROG: butter
LANG: C++     
*/
#include<set>  
#include<map>  
#include<list>  
#include<queue>  
#include<stack>  
#include<string>  
#include<math.h>  
#include<time.h>  
#include<vector>  
#include<bitset>  
#include<memory>  
#include<utility>  
#include<stdio.h>  
#include<sstream>  
#include<iostream>  
#include<stdlib.h>  
#include<string.h>  
#include<algorithm> 
#define LL unsigned long long   
using namespace std;
int n,p,c;//n:奶牛数，p:牧场数，c:道路数 
int x,a[801];//存每个点奶牛数量的 
int ai,bi,ci,i;//读入用的和循环控制变量 
int l,r,sum;//l:队首，r：队尾，sum：走的总距离 
int d[801];//存最短路的。 
int flag[801];//标记是否在队列中的 
struct haha
{
    int n;//存编号 
    int s;//存边权值 
}f[801][800];
int s[801];//s[i]表示点i连的边的条数 
int q[1600];
void in(int u,int v,int w)//插入
{
    s[u]++;
    s[v]++;
    f[u][s[u]].n=v;//伪邻接表，将边存进去 
    f[u][s[u]].s=w;
    f[v][s[v]].n=u;//双向边…… 
    f[v][s[v]].s=w;
}
int main() 
{
    freopen("butter.in","r",stdin);
    freopen("butter.out","w",stdout); 
    scanf("%d%d%d",&n,&p,&c);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&x);//读入牛的位置 
        a[x]++;//此位置的牛数量+1 
    }
    for (i=1;i<=c;i++)
    {
        scanf("%d%d%d",&ai,&bi,&ci);//读入边 
        in(ai,bi,ci);//存起来 
    }
    int Min=2333333;//min初始化 
    for (int ii=1;ii<=p;ii++)//枚举糖放置的位置 
    {
        x=ii;//提出来 
        for (i=1;i<=p;i++) 
        {
            d[i]=23333;
            flag[i]=0;
        }//初始化
        d[x]=0;
        l=0;//队列初始化 
        r=1;
        q[r]=x;//x入队 
        flag[x]=1;//标记 
        while (l!=r)
        {
            l++;//出队
            int xx=q[l];//挖出来 
            flag[xx]=0;//去标记 
            for (i=1;i<=s[xx];i++)//一个个点进行松弛操作 
                if (d[xx]+f[xx][i].s<d[f[xx][i].n])
                { 
                    d[f[xx][i].n]=d[xx]+f[xx][i].s;//更新 
                    if (flag[f[xx][i].n]==0)//没在队列中 
                    {
                        r++;//入队 
                        q[r]=f[xx][i].n;
                        flag[f[xx][i].n]=1;//标记 
                    } 
                }
        }
        sum=0;
        for (i=1;i<=p;i++) sum=sum+a[i]*d[i];//求和 
        if (sum<Min) Min=sum;//比较 
    }
    printf("%d\n",Min);//输出 
    return 0;
}