dijkstra之细节处理 ——PAT (Advanced Level) 1072 Gas Station (30 分)

本文主要是介绍dijkstra之细节处理 ——PAT (Advanced Level) 1072 Gas Station (30 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

题目大意：
有n个居民楼，m个汽油站，给出k条路，要选最合适的汽油站：
1.该汽油站满足到所有居民楼距离不超过ds
2.该汽油站到所有居民楼的最短距离尽可能大
3.在2相同情况下，该汽油站到所有居民楼的平均距离尽可能小
4.在3相同情况下，汽油站标号最小

变量准备：
为了做出dijkstra算法，需要提前设定dis,e,visit等变量，且需设置inf
同时注意设置的max值要大于n + m即1010

更细节的地方需要注意：
e[i][i]设置为0
e[i][j]的路径取最短的

利用singlemin_和avgmin_记录全局的个体最短的最长&平均距离最短的

//大型变量定义现场
int n, m, k, ds;
int e[1100][1100], dis[1100];
bool visit[1100];
int inf = 999999999;
double singlemin_ = -1, avgmin_ = inf;//全局的个体最短的最长&平均距离

输入处理：
输入当作string
将两类点放进1 - n + m, 其中前n个表示居民，后m个表示加油站
1.若无G，则直接stoi读入编号
2.若有G，利用substr(1)表示抓取第一个字符起到结尾的数字，令编号为n + stoi表示gas station

    //初始化准备fill(e[0], e[0] + 1100 * 1100, inf);fill(dis, dis + 1100, inf);for(int i = 0; i < 1100; i++) e[i][i] = 0;//输入处理cin >> n >> m >> k >> ds;string a, b;int c, d, dist;for(int i = 0; i < k; i++){cin >> a >> b >> dist;if(a[0] == 'G'){   a = a.substr(1);c = n + stoi(a);}else c = stoi(a);if(b[0] == 'G'){   b = b.substr(1);d = n + stoi(b);}else d = stoi(b);//cout << c << d << dist << endl;e[c][d] = e[d][c] = min(dist, e[c][d]);}

dijkstra过程：
每个gas来一次dijkstra，首先判断ds，然后记录最短距离和平均距离进行比较，dijkstra过程如下：
1.初始化起点dis为0
2.找出最小的dis记录为u和minn
3.visit为true
4.寻遍v，并更新新的dis[v]

    int nowid = -1;double singlemin, avgmin;//遍历每一个gas stationfor(int index = n + 1; index <= n + m; index++){   //初始化dis和visitfill(dis, dis + 1100, inf);fill(visit, visit + 1100, false);singlemin = inf;avgmin = 0;//dijkstra阶段dis[index] = 0;//index作为起点for(int i = 1; i <= n + m; i++){   int u = -1, minn = inf;//找出目前到index距离最短的for(int j = 1; j <= n + m; j++){if(visit[j] == false && dis[j] < minn){u = j;minn = dis[j];}}if(u == -1) break;visit[u] = true;//更新未选中的点到起点的距离for(int v = 1; v <= n + m; v++){if(visit[v] == false && dis[v] > dis[u] + e[u][v])dis[v] = dis[u] + e[u][v];}}//到目前为止，得到了dis的全部值//考察与每个居民楼的距离for(int i = 1; i <= n; i++){if(dis[i] > ds) //超出服务范围{singlemin = -1;break;}singlemin = min(singlemin, double(dis[i]));//最短距离avgmin += dis[i];//平均距离}if(singlemin == -1) continue;//不合最远服务要求avgmin = avgmin / n;//cout << singlemin << " " << avgmin << endl;if(singlemin > singlemin_){nowid = index;singlemin_ = singlemin;avgmin_ = avgmin;}else if(singlemin == singlemin_ && avgmin < avgmin_){nowid = index;avgmin_ = avgmin;}else if(singlemin == singlemin_ && avgmin == avgmin_)nowid = min(nowid, index);}

完整代码：

#include<bits/stdc++.h>
using namespace std;//大型变量定义现场
int n, m, k, ds;
int e[1100][1100], dis[1100];
bool visit[1100];
int inf = 999999999;
double singlemin_ = -1, avgmin_ = inf;//全局的个体最短&平均距离int main()
{   //初始化准备fill(e[0], e[0] + 1100 * 1100, inf);fill(dis, dis + 1100, inf);for(int i = 0; i < 1100; i++) e[i][i] = 0;//输入处理cin >> n >> m >> k >> ds;string a, b;int c, d, dist;for(int i = 0; i < k; i++){cin >> a >> b >> dist;if(a[0] == 'G'){   a = a.substr(1);c = n + stoi(a);}else c = stoi(a);if(b[0] == 'G'){   b = b.substr(1);d = n + stoi(b);}else d = stoi(b);//cout << c << d << dist << endl;e[c][d] = e[d][c] = min(dist, e[c][d]);}int nowid = -1;double singlemin, avgmin;//遍历每一个gas stationfor(int index = n + 1; index <= n + m; index++){   //初始化dis和visitfill(dis, dis + 1100, inf);fill(visit, visit + 1100, false);singlemin = inf;avgmin = 0;//dijkstra阶段dis[index] = 0;//index作为起点for(int i = 1; i <= n + m; i++){   int u = -1, minn = inf;//找出目前到index距离最短的for(int j = 1; j <= n + m; j++){if(visit[j] == false && dis[j] < minn){u = j;minn = dis[j];}}if(u == -1) break;visit[u] = true;//更新未选中的点到起点的距离for(int v = 1; v <= n + m; v++){if(visit[v] == false && dis[v] > dis[u] + e[u][v])dis[v] = dis[u] + e[u][v];}}//到目前为止，得到了dis的全部值//考察与每个居民楼的距离for(int i = 1; i <= n; i++){if(dis[i] > ds) //超出服务范围{singlemin = -1;break;}singlemin = min(singlemin, double(dis[i]));//最短距离avgmin += dis[i];//平均距离}if(singlemin == -1) continue;//不合最远服务要求avgmin = avgmin / n;//cout << singlemin << " " << avgmin << endl;if(singlemin > singlemin_){nowid = index;singlemin_ = singlemin;avgmin_ = avgmin;}else if(singlemin == singlemin_ && avgmin < avgmin_){nowid = index;avgmin_ = avgmin;}else if(singlemin == singlemin_ && avgmin == avgmin_)nowid = min(nowid, index);}//最终输出if(nowid == -1) printf("No Solution\n");else {printf("G%d\n", nowid - n);printf("%.1lf %.1lf\n", singlemin_, avgmin_ + 0.001);}return 0;
}