1.题目要求一个加油站，能够到达所有的屋子，并且这个加油站到屋子的最小距离尽可能地大（实际上也应该，不然汽油挥发会影响人身安全啊啊啊）。
2.根据汽油站index排序时，不能使用string，要转换成int排序，避免出现G1<G123<G2<G23这样的情况。
3.通过dijkstra求每个加油站到各个屋子的距离，即dijkstra外加一个循环遍历。然后统计所有的最短路径和平均路径，进行排序。
4.最小距离一样的，根据平均距离来排序，平均距离仍然一样的，根据加油站的id来排序。
5.为了提高空间利用率，把加油站和屋子都统一成一个结构体，这个结构体数据的0~housesum用来表示屋子，housesum+1~housesum+1+gassum表示加油站。
A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range.
Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution is still not unique, output the one with the smallest index number.
Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive integers: N (<= 103), the total number of houses; M (<= 10), the total number of the candidate locations for the gas stations; K (<= 104), the number of roads connecting the houses and the gas stations; and DS, the maximum service range of the gas station. It is hence assumed that all the houses are numbered from 1 to N, and all the candidate locations are numbered from G1 to GM.
Then K lines follow, each describes a road in the format
P1 P2 Dist
where P1 and P2 are the two ends of a road which can be either house numbers or gas station numbers, and Dist is the integer length of the road.
Output Specification:
For each test case, print in the first line the index number of the best location. In the next line, print the minimum and the average distances between the solution and all the houses. The numbers in a line must be separated by a space and be accurate up to 1 decimal place. If the solution does not exist, simply output “No Solution”.
Sample Input 1:
4 3 11 5 1 2 2 1 4 2 1 G1 4 1 G2 3 2 3 2 2 G2 1 3 4 2 3 G3 2 4 G1 3 G2 G1 1 G3 G2 2
Sample Output 1:
G1 2.0 3.3
Sample Input 2:
2 1 2 10 1 G1 9 2 G1 20
Sample Output 2:
No Solution
[c language=”++”]
//#include<string>
//#include<stack>
//#include<unordered_set>
//#include <sstream>
//#include "func.h"
//#include <list>
#include <iomanip>
#include<unordered_map>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include <algorithm>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<stack>
using namespace std;
/*
2 1 2 20
1 G1 9
2 G1 20
1 1 1 20
1 G1 9
4 3 11 5
1 2 2
1 4 2
1 G1 5
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
*/
struct Node{
vector<pair<int,int>> list;//邻居
bool visited;
bool sured;
long long cost;
Node() :list(0), visited(false), sured(false), cost(INT_MAX){};
};
string num2string(int a)
{
if (a == 0) return "0";
string ans = "";
while (a != 0)
{
char c = a % 10 + ‘0’;
ans = c + ans;
a /= 10;
}
return ans;
}
struct resultNode{
string gas;//不能够用string排序，避免G1,G123,G2,G23这样的情况
int id;
double min;
double avg;
double totalCost;
resultNode(string s,int i, double m, double a) :gas(s), id(i), min(m), avg(a), totalCost(0){};
resultNode() :gas(""), id(0), min(0), avg(0), totalCost(0){};
};
bool cmp(const resultNode&a, const resultNode&b)
{
if (a.min > b.min)
return true;
else if (a.min == b.min && a.totalCost < b.totalCost)
return true;
else if (a.min == b.min && a.totalCost == b.totalCost && a.id < b.id)
return true;
else return false;
}
int main(void)
{
int houseSum, gasSum, roadSum, serviceRange;
cin >> houseSum>> gasSum>>roadSum>>serviceRange;
vector<Node> place( houseSum+gasSum+1);//1~houseSum表示房子，houseSum+1~houseSum+gasSum表示加油站
map<int,bool> gasStationNum;
for (int i = 0; i < roadSum; i++)
{
int a = 0;
char tmp[5];
scanf("%s", tmp);
if (tmp[0] == ‘G’)//加油站
{
a = 0;//1~houseSum表示房子，houseSum+1~houseSum+gasSum表示加油站
for (int j = 1; j < 5 && tmp[j] != 0; j++)
a = a * 10 + tmp[j] – ‘0’;
a += houseSum;//1~houseSum表示房子，houseSum+1~houseSum+gasSum表示加油站
}
else
{
a = 0;
for (int j = 0; j < 5 && tmp[j] != 0; j++)
a = a * 10 + tmp[j] – ‘0’;
}
int b = 0;
scanf("%s", tmp);
if (tmp[0] == ‘G’)//加油站
{
b = 0;//1~houseSum表示房子，houseSum+1~houseSum+gasSum表示加油站
for (int j = 1; j < 5 && tmp[j] != 0; j++)
b = b * 10 + tmp[j] – ‘0’;
b += houseSum;//1~houseSum表示房子，houseSum+1~houseSum+gasSum表示加油站
}
else
{
b = 0;
for (int j = 0; j < 5 && tmp[j] != 0; j++)
b = b * 10 + tmp[j] – ‘0’;
}
int cost;
scanf("%d", &cost);
place[a].list.push_back({ b, cost });
place[b].list.push_back({ a, cost });
}
double minCost = INT_MAX;
double totalCost = INT_MAX;
vector<resultNode> ans(0);
for (int nowGas = houseSum + 1; nowGas < houseSum + gasSum + 1; nowGas++)
{
bool canChoose = true;//记录是否能够选为加油站，后面服务范围会使用
long long thisMinCost = INT_MAX;
long long thisTotalCost = 0;
vector<Node> v = place;//避免统计每个加油站时，数据已经存在，所以每次计算加油站，都新建一个节点vector
//使用dijkstra算法统计单元最短路径
v[nowGas].visited = true;
v[nowGas].cost = 0;
while (1)
{
int p = -1;
for (int i = 0; i < v.size(); i++)
{
if (p == -1 && v[i].visited&&!v[i].sured)
p = i;
else if (p != -1 && v[i].visited && !v[i].sured && v[i].cost < v[p].cost)
p = i;
}
if (p == -1) break;
v[p].sured = true;
if (p <= houseSum && v[p].cost > serviceRange)
{//如果该点是房子，但是在服务距离之外，则false
canChoose = false;
break;
}
for (int i = 0; i < v[p].list.size(); i++)
{
int q = v[p].list[i].first;
if (!v[q].sured && v[q].cost > v[p].cost + v[p].list[i].second)
{
v[q].visited = true;//标记为已经探望
v[q].cost = v[p].cost + v[p].list[i].second;//更新最短路径
}
}
}
if (!canChoose) continue;//有些房子服务范围之外，不能选为gas
for (int i = 1; i <= houseSum; i++)
{//只统计房子部分，计算最短路径和总耗费
thisMinCost = min(thisMinCost, v[i].cost);
thisTotalCost += v[i].cost;
if (!v[i].sured)
{//有些房子没有到达，不能选为gas
canChoose = false;
break;
}
}
if (!canChoose) continue;//有些房子没有到达，不能选为gas
//存储结果
minCost = thisMinCost;
totalCost = thisTotalCost;
string gasID = "G";
gasID += num2string(nowGas – houseSum);
double avg = thisTotalCost*1.0 / houseSum;
ans.push_back(resultNode(gasID, nowGas – houseSum, thisMinCost, avg));
ans.back().totalCost = thisTotalCost;
}
if (ans.size() == 0)
printf("No Solution\n");
else
{
sort(ans.begin(), ans.end(), cmp);
cout << ans[0].gas << endl;
printf("%.1lf %.1lf\n", ans[0].min, ans[0].avg);
}
return 0;
}
[/c]