人活着系列Tanya和蔡健雅猪（floyd）

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

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个猪圈连通。

输出

演示样例输入

演示样例输出

提示

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

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

错误代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

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<n;i++)

    {

        scanf("%d",&mm);

        vis[mm] = 0;

    }

    for(int i = 0;i<k;i++)

    {

        scanf("%d%d%d",&a,&b,&c);

        if(vis[a]==1 || vis[b]==1) continue;

        edge[l].u = a; edge[l].v = b; edge[l++].w = c;

    }

     qsort(edge,l,sizeof(edge[0]),cmp);

      kruskal();

    return 0;

}

后台数据比較水

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#define INF 0x3f3f3f3f

using 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<KKK;i++)

    {

		scanf("%d%d%d",&u,&v,&w);

        ma[u][v]=ma[v][u]=w;

    }

    for( k=1; k<=m; k++)

	{

         for( i=1; i<=m; i++)

		 {

			 for( j=1; j<=m; j++)

            {

				if(ma[i][j] > 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;

}

/*****************************

人活着系列

人活着系列Tanya和蔡健雅猪 （floyd）