最短路径
题目大意
从m个加油站里面选取1个站点，让它和离它最近的居民区距离最远，并且没有超出服务范围ds之内。如果有很多个最远的加油站，输出距离所有居民区距离平均距离最小的那个。如果平均值还是一样，就输出加油站编号最小的那个。
思路
Dijkstra算法。注意每次调用Dijkstra都要初始化。 因为加油站之间也是彼此有路连接的，所以最短路径计算的时候也要把加油站算上。因此考虑将加油站和居民点放在一起，用Dijkstra时循环的范围时1~n+m。可以根据输入的是G还是数字来判断，如果是数字就令编号为他自己，如果是G开头的，编号设为n+G后面的数字。 我是先针对每个加油站调用一次Dijkstra，将满足可连通、没有超出服务范围的所有加油站及各项参数（最近点的距离、平均距离、加油站编号）存在另一个结构体中，再统一判断求最优解。（因为数据量<=10,我就直接图方便写了个排序。最近点距离较远->平均距离较短->加油站编号较小）
坑
坑点集中在最后一个测试点4： （1）加油站和居民点的输入按照string，然后转成数字时要注意它不仅是1位数，可能是多位数。（str.erase(str.begin()+x);中参数是迭代器！） （2）.1f%的输出会自动四舍五入，不用+0.05。
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define N 1020
#define INF 100000000
struct way {
double dis, min;
int index;
}ways[12];
int numways = 0;
struct node {
int v, distance;
};
vector<node>Adj[N];
int n, m;//1~n是居民点；n+1~n+m是加油站
int dis[N];
bool vis[N] = { false };
void Dijkstra(int s) {
int i, j;
for (i = 0;i < N;i++) {
dis[i] = INF;
vis[i] = false;
}
dis[s] = 0;
for (i = 0;i < n + m;i++) {
int min = INF, u = -1;
for (j = 1;j <= n + m;j++) {
if (min > dis[j] && vis[j] == false) {
min = dis[j];
u = j;
}
}
if (u == -1)return;
vis[u] = true;
for (j = 0;j < Adj[u].size();j++) {
int v = Adj[u][j].v;
if (vis[v] == false && dis[v] > dis[u] + Adj[u][j].distance) {
dis[v] = dis[u] + Adj[u][j].distance;
}
}
}
}
bool cmp(way a, way b) {
if (a.min != b.min)return a.min > b.min;
else if (a.dis != b.dis)return a.dis < b.dis;
else return a.index < b.index;
}
int strtoint(string a) {
int ans = 0;
for (int i = 0;i < a.size();i++)
ans = ans * 10 + a[i] - '0';
return ans;
}
int main() {
int i, j, k, dmax;
scanf("%d%d%d%d", &n, &m, &k, &dmax);
for (i = 0;i < k;i++) {
int p1, p2, dist;
string s_p1, s_p2;
cin >> s_p1 >> s_p2 >> dist;
if (s_p1[0] == 'G') {
s_p1.erase(s_p1.begin());
p1 = strtoint(s_p1) + n;
}
else p1 = strtoint(s_p1);
if (s_p2[0] == 'G') {
s_p2.erase(s_p2.begin());
p2 = strtoint(s_p2) + n;
}
else p2 = strtoint(s_p2);
node temp;
temp.distance = dist;
temp.v = p1;Adj[p2].push_back(temp);
temp.v = p2;Adj[p1].push_back(temp);
}
for (i = n + m;i > n;i--) {
Dijkstra(i);
for (j = 1;j <= n;j++)
if (dis[j] > dmax)break;
if (j == n + 1) {//符合条件的路径存在
ways[numways].index = i - n;
int dmin = INF;
for (k = 1;k <= n;k++) {//计算总路径长和最小路径值
if (dmin > dis[k])dmin = dis[k];
ways[numways].dis += dis[k];
}
ways[numways].min = dmin;
ways[numways].dis = ways[numways].dis / n;
numways++;
}
}
if (numways == 0)printf("No Solution\n");
else {
sort(ways, ways + numways, cmp);//顺手写了个排序，其实duck不必。找最小值就好了~
printf("G%d\n%.1f %.1f\n", ways[0].index, ways[0].min, ways[0].dis);
}
return 0;
}
