一、题目概述
给定N个居民区和M个加油站备选址，即各点间的距离。在M个油站备选址中找到最合适的一处。
油站选址标准：
1、N个居民区都在服务范围内。
2、距最短距离尽可能的远。
3、若有另一油站距居民区最短距离相同，选择距离居民区平均距离最短的。
二、思路
1、关于图的建立
（1）存储为邻接矩阵无向图，居民区下标1~N，油站下标N + 1 ~ N + M;
（2）用string读入居民区或油站的下标，若str以G开头，取G后面的数字再加N（小心G10时，G后是两位数），是油站下标；若str不以G开头，仅转换为数字，是居民区下标。
2、关于距离计算
从N + 1到N + M调用M次dijkstra算法，求单源最短路径，并统计最大距离和最小距离。
若最大距离超过Ds，说明有居民区不在服务范围，排除；
然后依次比较，找到最终油站位置。
三、代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
using namespace std;
#define INF 0x7FFFFFFF
int main()
{int N, M, Ds, K, ans = -1, max_ans, min_ans = 0;double ave_ans;vector<vector<int>> G( 1011, vector<int>(1011, INF) );scanf("%d %d %d %d", &N, &M, &K, &Ds);for( int i = 0, p[2], d; i < K; ++i ){for( int j = 0; j < 2; ++j ){string str;cin >> str;if( str[0] == 'G' )p[j] = atoi( str.substr( 1, 2 ).c_str() ) + N;else p[j] = atoi( str.c_str() );}scanf("%d", &d);G[ p[0] ][ p[1] ] = G[ p[1] ][ p[0] ] = d;}for( int i = N + 1; i <= M + N; ++i ){vector<int> dist(1011, INF), vset(1011, 0);dist[i] = 0;for( int j = 1, v, min; j <= M + N; ++j ){min = INF;for( int k = 1; k <= M + N; ++k )if( !vset[k] && dist[k] < min ){v = k;min = dist[k];}if( min == INF )break;vset[v] = 1;for( int k = 1; k <= M + N; ++k )if( G[v][k] != INF && dist[v] + G[v][k] < dist[k] )dist[k] = dist[v] + G[v][k];}int min_l = INF, max_l = 0;double ave = 0;for( int j = 1; j <= N; ++j ){ave += dist[j];if( dist[j] < min_l )min_l = dist[j];if( dist[j] > max_l )max_l = dist[j];}ave /= N;if( max_l <= Ds && ( min_l > min_ans || ( min_l == min_ans && ave < ave_ans ) ) ){ans = i;min_ans = min_l;max_ans = max_l;ave_ans = ave;}}if( ans == -1 )printf("No Solution");else printf("G%d\n%d.0 %.1f", ans - N, min_ans, ave_ans);
}