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

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 52341 2 11 3 52 3 72 4 33 4 5

演示样例输出

8

提示

開始以为，崔老师坑我们，不是最短路，就打成了最小生成树。kurskal

感觉思路没错，没有的猪圈。就不加边。╮(╯▽╰)╭，挂了20遍。没过

错误代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          const int INF = 65535;using namespace std;struct node{    int u,v,w;}edge[1300];int n,m,father[610],l;bool vis[610];int cmp(const void *a ,const void *b){    struct node *X,*Y;    X = (struct node *)a;    Y = (struct node *)b;    return X->w - Y->w;}void init(){    l = 0;    for(int i = 0;i<=m;i++)        father[i] = i;}int findx(int r){    int i ,j;    while(r!=father[r])    {         r= father[r];    }    i = r;    while(father[i]!=r)    {        j = father[i];        father[i] = r;        i = j;    }    return r;}void kruskal(){    int ans = 0;    for(int i = 0;i<=l;i++)    {         int uu = findx(edge[i].u);         int vv = findx(edge[i].v);       //  printf("%d->%d = %d\n",edge[i].u,edge[i].v,edge[i].w);         if(uu!=vv)            {                father[uu] = vv;                ans += edge[i].w;            }    }    printf("%d\n",ans);}int main(){    int mm, a , b,c,k;    scanf("%d%d%d",&n,&m,&k);    init();    for(int i = 1;i<=m;i++)        vis[i] = 1;    for(int i = 0;i
         
        
       
      

AC

后台数据比較水

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define INF 0x3f3f3f3fusing namespace std;int n,m,KKK;int ma[651][651],a[400];void init(){	int i,j;   for(i=1; i<=m;i++)    {        for( j=1; j<=m; j++)		{			if(i==j) ma[i][j] = 0;			else ma[i][j]=INF;		}    }}int main(){    int u,v,w,i,j,k;	scanf("%d%d%d",&n,&m,&KKK);//puts("1");	init();    for(i=1; i<=n; i++)	{		scanf("%d",&a[i]);	}	for(i = 0;i
          
            ma[i][k] + ma[k][j])				{					ma[i][j] = ma[i][k] + ma[k][j];				}            }		 }	}    int sum , mi = INF;    for(i=1; i<=m; i++)    {        sum=0;        for(j=1; j<=n; j++)		{			sum += ma[i][a[j]];		}        if(sum < mi)            mi = sum;    }    printf("%d\n",mi);    return 0;} /*****************************
          
         
        
       
      

版权声明：本文博客原创文章。博客，未经同意，不得转载。