http://ac.jobdu.com/problemset.php?page=4
floyd算法，只要看新修建的路不是不可以加入其中已经存在的某条最短路中，使之更短就可以了
1 #include <stdio.h>
2 #include <stdlib.h>
3 int N,K;
4 int mat[302][302];
5 int calc()
6 {
7 int i,j;
8 int sum=0;
9 for(i=1;i<=N;i++)
10 for(j=i+1;j<=N;j++)
11 sum+=mat[i][j];
12 return sum;
13 }
14 int main()
15 {
16 while(scanf("%d",&N)!=EOF){
17 int i,j,k;
18 for(i=1;i<=N;i++)
19 for(j=1;j<=N;j++){
20 scanf("%d",&mat[i][j]);
21 }
22 scanf("%d",&K);
23 for(k=1;k<=K;k++){
24 int a,b,w;
25 scanf("%d%d%d",&a,&b,&w);
26 for(i=1;i<=N;i++)
27 for(j=1;j<=N;j++){
28 if(mat[i][j]>mat[i][a]+w+mat[b][j]){
29 mat[i][j]=mat[i][a]+w+mat[b][j];
30 mat[j][i]=mat[i][j];
31 }
32 }
33 printf("%d\n",calc());
34 }
35 }
36 }