1072 Gas Station(Dijkstra)

题目

要建一个加油站。
地图里有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:这道题花了我好长时间,但是也学到了很多)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,496评论 6 501
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,407评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,632评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,180评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,198评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,165评论 1 299
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,052评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,910评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,324评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,542评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,711评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,424评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,017评论 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,668评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,823评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,722评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,611评论 2 353

推荐阅读更多精彩内容

  • 140 - 家电类 Time Limit: 1000 Memory Limit: 65535 Submit: 1...
    z坎坷阅读 634评论 0 0
  • 第四天 数组【悟空教程】 第04天 Java基础 第1章数组 1.1数组概念 软件的基本功能是处理数据,而在处理数...
    Java帮帮阅读 1,598评论 0 9
  • Swift 函数用来完成特定任务的独立的代码块。Swift使用一个统一的语法来表示简单的C语言风格的函数到复杂的O...
    零度_不结冰阅读 321评论 0 0
  • 1.单行注释:“//”2.多行注释:“/ /” if条件语句 1. if(bloolean 表达式){pass;...
    再也不喊饿阅读 573评论 0 0
  • SwiftDay011.MySwiftimport UIKitprintln("Hello Swift!")var...
    smile丽语阅读 3,831评论 0 6