团体程序设计天梯赛
L3-005 垃圾箱分布
Dijkstra算法。使用邻接矩阵存储图。以每个候选点作为起始点执行一次Dijkstra算法，动态更新最长最短距离minDist和总距离sumDist. 需要注意C++和C的四舍五入略有不同，在C++中，0.5不能看作1，需要加上很小的值，如1e-6，将其进位为1.
Dijkstra算法：邻接矩阵cityMap，最短距离数组dist，访问标记数组visited，父节点数组pre(非必须)。在代码中将邻接矩阵主对角线的值赋为了INF,dist数组中初始节点的距离也为INF.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > cityMap;
vector<int> dist, visited;
const int INF = 99999;
int n, m, k, ds;
void dijk(int st){
for(int i = 1; i <= n + m; i++){
dist[i] = INF;
visited[i] = 0;
}
for(int i = 1; i <= n + m; i++) if(cityMap[st][i] != INF) dist[i] = cityMap[st][i];
visited[st] = 1;
for(int i = 0; i <= n + m - 2; i++){
int toUpdate = -1;
int minDist = INF;
for(int j = 1; j <= n + m; j++) if(visited[j] != 1 && dist[j] < minDist){
toUpdate = j;
minDist = dist[j];
}
if(toUpdate == -1) continue; // 非连通图
visited[toUpdate] = 1;
for(int j = 1; j <= n + m; j++)
if(visited[j] != 1 && dist[toUpdate] + cityMap[toUpdate][j] < dist[j])
dist[j] = dist[toUpdate] + cityMap[toUpdate][j];
}
}
int main(){
cin >> n >> m >> k >> ds;
cityMap.resize(n + m + 1);
for(int i = 1; i <= n + m; i++){
cityMap[i].resize(n + m + 1, INF);
}
dist.resize(n + m + 1);
visited.resize(n + m + 1);
for(int i = 0; i <= k - 1; i++){
string st, des;
int sti, desi, dist;
cin >> st >> des >> dist;
if(st[0] == 'G'){
st = st.substr(1);
sti = n + stoi(st);
}
else sti = stoi(st);
if(des[0] == 'G'){
des = des.substr(1);
desi = n + stoi(des);
}
else desi = stoi(des);
cityMap[sti][desi] = cityMap[desi][sti] = dist;
}
int choice = -1, minDist = 0, sumDist = 0;
for(int i = n + 1; i <= n + m; i++){
dijk(i);
int tempMinDist = INF, tempSumDist = 0;
for(int j = 1; j <= n; j++) {
if(dist[j] > ds){
tempMinDist = -1;
break;
}
tempSumDist += dist[j];
if(dist[j] < tempMinDist) tempMinDist = dist[j];
}
if(tempMinDist != -1){
if(tempMinDist > minDist){
choice = i - n;
minDist = tempMinDist;
sumDist = tempSumDist;
}
else if(tempMinDist == minDist){
if(tempSumDist < sumDist){
choice = i - n;
sumDist = tempSumDist;
}
else if(tempSumDist == sumDist){
continue;
}
}
}
}
if(choice == -1) cout << "No Solution" << endl;
else{
cout << 'G' << choice << endl;
cout << setiosflags(ios::fixed) << setprecision(1) << (double)minDist << ' ' << ((double)sumDist+(1e-6)) / n << endl;
}
return 0;
}