http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2929
这个题一方面数据水，另一方面就是思维水，一拿到题就以为考最小生成树。
因为这个题需要求各点间的距离，又因为猪圈的数目最大为600，所以根本就没寻思考Floyd,一方面思维，另一方面是水的后台，因为猪每天去固定的猪圈吃饭，所以求出每个猪到每个猪圈固定的距离便可。
WA（以为已经求出各点间的最短距离，只要猪圈没猪便不会去）
反例
3 4 3
2
3
4
1 2 1
1 3 1
1 4 1
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define N 1000001
using namespace std;
int map[][],dis[],v[];
int n,m,k,a[],V;
void Floy()
{
for(int k=; k<=m; k++)
{
for(int j=; j<=m; j++)
{
for(int i=; i<=m; i++)
{
if(map[j][i]>map[j][k]+map[k][i])
{
map[j][i]=map[j][k]+map[k][i];
}
}
}
}
}
void prim()
{
memset(v,,sizeof(v));
for(int i=; i<=m; i++)
dis[i]=map[a[]][i];
v[a[]]=;
int min,k;
int sum=;
for(int i=; i<V; i++)
{
min=N;
for(int j=; j<=m; j++)
{
if(v[j]==&&dis[j]<min)
{
min=dis[j];
k=j;
}
}
v[k]=;
//printf("min==%d\n",min);
sum=sum+min;
for(int j=; j<=m; j++)
{
if(v[j]==&&dis[j]>map[k][j])
{
dis[j]=map[k][j];
}
}
}
printf("%d\n",sum);
}
int main()
{
int xx[],yy[],zz[];
int sum,sum1;
scanf("%d%d%d",&n,&m,&k);
for(int i=; i<=m; i++)
{
for(int j=; j<=m; j++)
{
map[i][j]=N;
map[j][i]=N;
}
map[i][i]=;
}
int b[];
V=;
memset(b,,sizeof(b));
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
b[a[i]]++;
}
for(int i=; i<=m; i++)
{
if(b[a[i]])
V++;
}
for(int i=; i<=k; i++)
{
scanf("%d%d%d",&xx[i],&yy[i],&zz[i]);
if(zz[i]<map[xx[i]][yy[i]])
{
map[xx[i]][yy[i]]=zz[i];
map[yy[i]][xx[i]]=zz[i];
}
}
Floy();
/*for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}*/
for(int i=; i<=k; i++)
{
sum=;
sum1=;
for(int j=; j<=n; j++)
{
if(xx[i]==a[j]) sum++;
if(yy[i]==a[j]) sum1++;
}
if(sum==)
{
for(int k=; k<=m; k++)
{
map[xx[i]][k]=N;
map[k][xx[i]]=N;
}
map[xx[i]][xx[i]]=;
}
if(sum1==)
{
for(int k=; k<=m; k++)
{
map[yy[i]][k]=N;
map[k][yy[i]]=N;
}
map[yy[i]][yy[i]]=;
}
if(sum&&sum1)
{
map[xx[i]][yy[i]]=sum*map[xx[i]][yy[i]];
map[yy[i]][xx[i]]=sum1*map[yy[i]][xx[i]];
}
}
prim();
}
return ;
}
AC的
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define N 1000001
using namespace std;
int n,m,k;
int a[],map[][];
void Floy()
{
for(int k=; k<=m; k++)
{
for(int i=; i<=m; i++)
{
for(int j=; j<=m; j++)
{
if(map[i][j]>map[i][k]+map[k][j])
{
map[i][j]=map[i][k]+map[k][j];
}
}
}
}
}
int main()
{
int xx,yy,zz;
scanf("%d%d%d",&n,&m,&k);
for(int i=; i<=n; i++)
scanf("%d",&a[i]);
for(int i=; i<=m; i++)
{
for(int j=; j<=m; j++)
{
map[i][j]=N;
map[j][i]=N;
}
map[i][i]=;
}
while(k--)
{
scanf("%d%d%d",&xx,&yy,&zz);
if(map[xx][yy]>zz)
{
map[xx][yy]=zz;
map[yy][xx]=zz;
}
}
Floy();
int min=N;
int sum;
for(int i=; i<=m; i++)
{
sum=;
for(int j=; j<=n; j++)
{
sum=sum+map[a[j]][i];
}
if(min>sum)
min=sum;
}
printf("%d\n",min);
return ;
}