大致题意就是给出 N 个房屋,M个加油站,K 个房屋(加油站)与房屋(加油站)之间的距离,以及加油站的最大服务距离DS。要求找到这样的加油站,即所有房屋处在其服务范围内,并且离该加油站最近的房屋的距离,在其它方案中的是最大的最近距离;如果该最近距离相同,那么要求该加油站距离所有房屋的平均距离最小;如果仍然相同,那么选择最小的加油站编号。
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 const int maxn = 1020; 5 const int inf = 1000000000; 6 int N,M,K,DS,G[maxn][maxn]; 7 bool visited[maxn] = {false}; 8 int d[maxn]; 9 10 void Dijkstra(int s) { 11 fill(visited,visited+maxn,false);//初始化 12 fill(d,d+maxn,inf); 13 d[s] = 0; 14 for(int i = 0; i < N+M; ++i) { 15 int u = -1, MIN = inf; 16 for(int j = 1; j <= N+M; ++j) { 17 if(visited[j] == false && d[j] < MIN) { 18 u = j; 19 MIN = d[j]; 20 } 21 } 22 if(u == -1) return ; 23 visited[u] = true; 24 for(int v = 1; v <= N+M; ++v) { 25 if(visited[v] == false && G[u][v] != inf) 26 if(d[u] + G[u][v] < d[v]) 27 d[v] = d[u] + G[u][v]; 28 } 29 } 30 } 31 32 int getId(string str) { 33 if(str[0] == 'G') return stoi(str.substr(1,-1))+N; 34 return stoi(str); 35 } 36 37 int main() { 38 cin>>N>>M>>K>>DS; 39 fill(G[0],G[0]+maxn*maxn,inf); 40 string c1,c2; 41 for(int i = 0; i < K; ++i) { 42 cin>>c1>>c2; 43 int u = getId(c1); 44 int v = getId(c2); 45 cin>>G[u][v]; 46 G[v][u] = G[u][v]; 47 } 48 double ansDis = -1,ansAvg = inf; 49 int ansID = -1; 50 for(int i = N+1; i <= N+M; ++i) { //枚举所有 加油站G 51 double minDis = inf,avg = 0; 52 Dijkstra(i); 53 for(int j = 1; j <= N; ++j) { //枚举所有 房屋,找到房屋到加油站的最短距离 54 if(d[j] > DS) { //存在,超出加油站的服务范围 55 minDis = -1; 56 break; 57 } 58 if(d[j] < minDis) minDis = d[j]; 59 avg += 1.0*d[j]/N; 60 } 61 if(minDis == -1) continue; 62 if(minDis > ansDis) { //更新最大的最短距离 63 ansDis = minDis; 64 ansID = i; 65 ansAvg = avg; 66 } else if(ansDis == minDis && avg < ansAvg) { 67 ansID = i; 68 ansAvg = avg; 69 } 70 } 71 if(ansID == -1) printf("No Solution"); 72 else printf("G%d\n%.1f %.1f",ansID-N,ansDis,ansAvg); 73 return 0; 74 }