题意：n,m,k，有n个村庄，有k条路，每个村庄有个电话亭，现在要在这些村庄中设一个中心电话亭，每个村庄的快递员需要带中心村庄报道然后返回（有向图），有m台电话，如果村庄配置电话的话就不需要去报道，求快递员最少总共走了多少路
思路：先用floyd预处理下，然后求到每个村庄的最短路总和，比较最小的，这个就是中心电话亭，然后将这些和由大到小排序，，减去前m大的
#include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#include <math.h>#include <queue>using namespace std;const double eps = 1e-6;const int maxn = 200;const int INF = 10000000;int dis[maxn][maxn];int n, m , k; void floyd(){for(int k = 0; k < n; k++)for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)dis[i][j] = min(dis[i][j],dis[i][k]+ dis[k][j]); } int main(){#ifdef xxzfreopen("in.txt","r",stdin);#endif // xxzint Case = 1;while(~scanf("%d%d%d",&n,&m,&k)){for(int i = 0; i < n ; i++)for(int j = 0; j < n; j++)i == j ? dis[i][j] = 0 : dis[i][j] = INF;for(int i = 0; i < k; i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);dis[a- 1][b – 1] = c;}floyd();int Min = INF*200, flag = 0;for(int i = 0; i < n; i++){int sum = 0;for(int j = 0; j < n; j++){sum += dis[i][j] + dis[j][i];}if(sum < Min) flag = i, Min = sum;}int temp[200];for(int i = 0; i < n; i++){temp[i] = dis[flag][i] + dis[i][flag];}sort(temp,temp+n,greater<int>());for(int i = 0 ; i < m; i++)Min -= temp[i];printf("Case %d:\n",Case++);Min > INF ? printf("No solution\n") : printf("%d\n",Min);}return 0;}
失败是什么?没有什么，只是更走近成功一步;
