1072 Gas Station（Dijkstra）
2020-04-10 本文已影响0人
胖胖的熊管家
题目
要建一个加油站。
地图里有N个房子，M个加油站备选地址，K条道路连接他们，而且有一参数Ds是加油站的服务范围长度。
目标：找到能够最短到达各个房子的备选加油站。
输入：
| 行数 | 数字含义 | |||
|---|---|---|---|---|
| 第一行 | N 房子数 | M备选加油站数 | K 道路数 | Ds 服务范围 |
| 第二行 | 起点 | 终点 | 之间的距离 | |
| 第三行 | 起点 | 终点 | 之间的距离 | |
| 第...行 | 起点 | 终点 | 之间的距离 | |
| 第(K+1)行 | 起点 | 终点 | 之间的距离 |
输出：
| 行数 | 数字 | 含义 |
|---|---|---|
| 第一行 | 最短的加油站 | |
| 第二行 | 某房子到该加油站的最短路径 | 各房子到该加油站的平均路径 |
输出要求：
1.如果有多个答案，优先输出平均路径短的
2.如果连平均路径都一样，那就优先输出index小的
3.如果没有答案，输出“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++
思路：
与1003分析过的差不多。主要步骤就是1.初始化；2.Dijkstra核心算法；3.输出结果。
源码：
#include <iostream>
#include <cstdio>
#include <math.h>
#include<vector>
#include <string.h>
#include <sstream>
using namespace std;
int main() {
//----------------------------Init--------------
int N,M,K,Ds;
scanf("%d %d %d %d",&N,&M,&K,&Ds);
const int INF = 999;
bool visited[1020];
int e[1020][1020],dis[1020];
fill(e[0], e[0] + 1020 * 1020, INF);
fill(dis, dis + 1020, INF);
fill(visited, visited + 1020, false);
//gas station名字转化为数字与house一起储存在图里
string p1,p2;
int length;
for(int i=1;i<=K;i++){
cin>>p1>>p2>>length;
int c1,c2;
if(p1[0] == 'G'){
c1 = stoi(p1.substr(1))+N;
}
else{
c1 = stoi(p1);
}
if(p2[0] == 'G'){
c2 = stoi(p2.substr(1))+N;
}
else{
c2 = stoi(p2);
}
e[c1][c2] = e[c2][c1] = length;
}
//----------------------------Start--------------
double finalMin=-1,finalAve=INF;
int result=-1;
for(int n=N+1;n<=N+M;n++){
double minPath=INF,avePath=0;
fill(dis,dis+1020,INF);
fill(visited, visited + 1020, false);
dis[n]=0;
//dijkstra核心代码
for(int i=0;i<N+M;i++){
int u=-1,shortest=INF;
for(int j=1;j<=N+M;j++){
if(visited[j] == false && dis[j]<shortest){
shortest = dis[j];
u=j;
}
}
visited[u] = true;
if(u == -1) break;
for (int v=1; v<=N+M; v++) {
if(visited[v] == false && e[u][v] + dis[u] < dis[v]){
dis[v] = e[u][v]+dis[u];
}
}
}
//----------------------------End Print--------------
//计算要输出的结果
for (int i=1;i<=N;i++) {
if(dis[i] > Ds){
minPath = -1;
break;
}
if(dis[i] < minPath){
minPath = dis[i];
}
avePath += 1.0 * dis[i];
}
if (minPath == -1) {
continue;
}
avePath = avePath / N;
if(minPath > finalMin){
result = n;
finalMin = minPath;
finalAve = avePath;
}
else if (minPath == finalMin && avePath < finalAve){
result = n;
finalAve = avePath;
}
}
//按要求输出结果
if(result == -1){
cout<<"No Solution"<<endl;
}
else{
// if(result > N){
// cout<<"G"+to_string(result-N)<<endl;
// printf("%.1f %.1f",finalMin,finalAve);
// }
// else{
// cout<<result<<endl;
// printf("%.1f %.1f",finalMin,finalAve);
// }
//最好不要在同一个程序中同时使用cout和printf，有时候会出现问题。 ——《算法笔记》
printf("G%d\n%.1f %.1f", result-N,finalMin,finalAve);
}
return 0;
}
知识点+坑：
1.int和string的互相转化
string ---> int | atoi() ;stoi()
对c++标准库中字符串转化为int的两个函数 atoi() 和 stoi() 两个函数。
stoi用来转哈string的，atoi转化的是char.
char[]转string可以直接赋值或者用一个循环string--->int | to_string()
to_string(value) int转为string
2. 不要在同一个程序中同时使用cout和printf，有时候会出现问题。 ——《算法笔记》
坑坑坑！！
（前情：我用的是xcode）
1.xcode中对于C++用变量设置数组大小的初始化是不会报错的！！！
！！！不能用变量来初始化数组大小！！！
2.对于设置数组大小，比如在这道题中，我本来设的是1000，并没有设大，所以提交的时候最后一个测试点总是过不了。
报的错是“段错误”，看了《算法笔记》，说直接原因是非法访问了内存，例如数组越界、指针乱指，所以：
！！！这种数组初始化都要设大一点！！！
3.xcode中scanf保留一位小时%.1f没有四舍五入，它好像是去尾的！！不过在平台提交是正常的。
4.这个坑超级坑人，直到现在也不知道他的问题是什么。
坑就是代码中把gas station “Gx”转为数字像house一样存储。
原本我是这么写的：
string p1,p2;
int length;
for(int i=1;i<=K;i++){
cin>>p1>>p2>>length;
int c1,c2;
if(p1[0] == 'G'){
c1 = stoi(p1.substr(1))+N;
}
else if(p2[0] == 'G'){
c2 = stoi(p2.substr(1))+N;
}
else{
c1 = stoi(p1);
c2 = stoi(p2);
}
e[c1][c2] = e[c2][c1] = length;
}
但是不是太明白为什么这样不行，感觉让图e[][]构造错了，但是麻烦一点多个if判断就行了，不知道为什么（如果有网友知道的话，希望可以留言/私信告诉我）
string p1,p2;
int length;
for(int i=1;i<=K;i++){
cin>>p1>>p2>>length;
int c1,c2;
if(p1[0] == 'G'){
c1 = stoi(p1.substr(1))+N;
}
else{
c1 = stoi(p1);
}
if(p2[0] == 'G'){
c2 = stoi(p2.substr(1))+N;
}
else{
c2 = stoi(p2);
}
e[c1][c2] = e[c2][c1] = length;
}
（PS：这道题花了我好长时间，但是也学到了很多）
