题目没什么好说，最小生成树。。。再次NC的把更新策略写成了dij的：len[i]=len[pos]+map[pos][i]，该打该打。。
1
# include <stdio.h>
2# include <string.h>
3# define N 55
4int map[N][N];
5int len[N];
6int main()
7
{
8
int n,r,i;
9 while(1)
10
{
11 int res=0;
12 scanf("%d%d",&n,&r);
13 memset(map,-1,sizeof(map));
14 if(!n) break;
15 while(r--)
16 {
17 int a,b,l;
18 scanf("%d%d%d",&a,&b,&l);
19 if(map[a][b]==-1||map[a][b]>l)
20 map[a][b]=map[b][a]=l;
21
}
22 memset(len,-1,sizeof(len));
23 len[1]=0;
24 for(i=1;i<=n;i++)
25 {
26 int j,min=0xfffffff,pos;
27 for(j=1;j<=n;j++)
28 if(len[j]>=0&&len[j]<min)
29 min=len[j],pos=j;
30 res+=len[pos];
31 len[pos]=-2;
32 for(j=1;j<=n;j++)
33 if(map[pos][j]!=-1&&(len[j]==-1||len[j]>map[pos][j]))
34 len[j]=map[pos][j];
35 }
36 printf("%d\n",res);
37 }
38 return 0;
39
}
40