题意：
一个加油站必须建在这样一个位置，即车站和任何住宅区之间的最小距离尽可能远。然而，它必须保证所有的房屋都在服务范围内。 现在给出了城市地图和加油站的几个候选地点，你应该给出最好的建议。如果有一个以上的解决方案，输出一个最小的平均距离到所有的房子。如果这样的解决方案仍然不是唯一的，那么输出最小加油站标号的一个。
采用Dijkstra法：
// // main.cpp // PATA1072 // // Created by Phoenix on 2018/2/17. // Copyright © 2018年 Phoenix. All rights reserved. // #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int maxn = 1020; const int inf = 1000000000; int n, m, k, Ds; int G[maxn][maxn]; int d[maxn]; void dijkstra(int s) { fill(d, d + maxn, inf); bool vis[maxn] = {false}; d[s] = 0; for(int i = 0; i < n + m; i++) { int u = -1, MIN = inf; for(int j = 1; j <= n + m; j++) { if(vis[j] == false && d[j] < MIN) { u = j; MIN = d[j]; } } if(u == -1) return; vis[u] = true; for(int v = 1; v <= n + m; v++) { if(vis[v] == false && G[u][v] != inf && d[u] + G[u][v] < d[v]) { d[v] = d[u] + G[u][v]; } } } } int main(int argc, const char * argv[]) { scanf("%d %d %d %d", &n, &m, &k, &Ds); fill(G[0], G[0] + maxn * maxn, inf); for(int i = 0; i < k; i++) { char a[5], b[5]; int dis, s1 = 0, s2 = 0; scanf("%s %s %d", a, b, &dis); if(a[0] == 'G') { for(int i = 1; i < strlen(a); i++) { s1 = s1 * 10 + a[i] - '0'; } s1 += n; } else { for(int i = 0; i < strlen(a); i++) { s1 = s1 * 10 + a[i] - '0'; } } if(b[0] == 'G') { for(int i = 1; i < strlen(b); i++) { s2 = s2 * 10 + b[i] - '0'; } s2 += n; } else { for(int i = 0; i < strlen(b); i++) { s2 = s2 * 10 + b[i] - '0'; } } G[s1][s2] = G[s2][s1] = dis; } int gas = -1, mindis, avedis; int opt = 0, ave = inf; for(int i = n + 1; i <= n + m; i++) { dijkstra(i); int total = 0, mind = inf; bool flag = true; for(int j = 1; j <= n; j++) { total += d[j]; if(d[j] > Ds) flag = false; if(d[j] < mind && d[j] > 0) mind = d[j]; } if(flag == true){ if(mind > opt){ gas = i - n; mindis = mind; avedis = total; opt = mind; } else if(mind == opt) { if(total < avedis) { gas = i - n; avedis = total; } } } } if(gas == -1) printf("No Solution\n"); else { printf("G%d\n", gas); printf("%.1f %.1f\n", 1.0 * mindis, 1.0 * avedis / n ); } return 0; }
