人活着系列之芳姐和芳姐的猪

分手后的思念是犯贱 2022-08-18 02:35 124阅读 0赞

## 人活着系列之芳姐和芳姐的猪 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

芳姐特别喜欢猪，所以，她特意养了m个猪圈，顺便在k条无向边，每条边有都有起点v，距离.....芳姐和猪们约定好，每天去一个固定猪圈去吃饭，芳姐为了不累着她可爱的猪们，想知道所有的猪吃饭走的最短路程是多少？

## 输入 ##

第一行 ,猪的个数 m（ k(1<=k<=1200).（猪的编号为 1..m)

N+1行N头猪所在的猪圈号第n+k+1行：u、1<=w<=255)

m个猪圈连通。

## 输出 ##

## 示例输入 ##

3 4 5
    2
    3
    4
    1 2 1
    1 3 5
    2 3 7
    2 4 3
    3 4 5

## 示例输出 ##

## 提示 ##

## 来源 ##

## 示例程序 ##

#include <stdio.h>  
    #include <string.h>  
    #include <stdlib.h>  
    #include <algorithm>  
    #include <iostream>  
    #include <queue>  
    using namespace std;  
    #define inf 999999999  
    struct node  
    {  
        int v,w;  
        int next;  
    } edge[10010];  
    int head[1010];  
    int dis[1010][1010];//这里不同于其他的spfa，要用二维数组；  
    int vis[1010];  
    int same[1010];//因为有的是一个猪圈住好几个猪或者一个都不住，用same存储猪圈猪的个数；  
    int cnt,n,m;  
    void add(int u,int v,int w)  
    {  
        edge[cnt].v=v;  
        edge[cnt].w=w;  
        edge[cnt].next=head[u];  
        head[u]=cnt++;  
    }  
      
    void spfa(int s)  
    {  
        int i;  
        queue<int>q;  
        for(i=1; i<=m; i++)  
        {  
            dis[s][i]=inf;  
        }  
        memset(vis,0,sizeof(vis));  
        q.push(s);  
        dis[s][s]=0;  
        vis[s]=1;  
        while(!q.empty())  
        {  
            int u=q.front();  
            q.pop();  
            vis[u]=0;  
            for(i=head[u];i!=-1;i=edge[i].next)  
            {  
                int v=edge[i].v;  
                if(dis[s][v]>dis[s][u]+edge[i].w)  
                {  
                    dis[s][v]=dis[s][u]+edge[i].w;  
                    if(!vis[v])  
                    {  
                      q.push(v);  
                      vis[v]=1;  
                    }  
                }  
            }  
        }  
    }  
    int main()  
    {  
        int k,i,j,t;  
        int u,v,w;  
        int sum;  
        while(~scanf("%d %d %d",&n,&m,&k))  
        {  
            cnt=0;  
            memset(head,-1,sizeof(head));  
            memset(same,0,sizeof(same));  
            for(i=1;i<=n;i++)  
            {  
                scanf("%d",&t);  
                same[t]++;  
            }  
            for(i=1;i<=k;i++)  
            {  
                scanf("%d %d %d",&u,&v,&w);  
                add(u,v,w);  
                add(v,u,w);  
            }  
            for(i=1;i<=m;i++)//求每个顶点的最短路  
            {  
                spfa(i);  
            }  
            int minx=inf;  
            for(i=1;i<=m;i++)  
            {  
                sum=0;  
                for(j=1;j<=m;j++)  
                {  
                    if(same[j]!=0)  
                        sum+=dis[i][j]*same[j];  
                }  
                if(minx>sum)  
                minx=sum;  
            }  
            printf("%d\n",minx);  
        }  
        return 0;  
    }