【PAT甲级】Dijkstra专题复习

╰半橙微兮° 2023-02-23 08:13 60阅读 0赞

Dijkstra专题近三年考察情况：19年9月第四题（题解在此：[https://blog.csdn.net/allisonshing/article/details/100643092][https_blog.csdn.net_allisonshing_article_details_100643092]）

笔记：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70][]

## liuchuo满分代码展示 ##

### 1111 Online Map (30分) ###

[https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856][https_pintia.cn_problem-sets_994805342720868352_problems_994805358663417856]

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const int inf = 999999999;
    int dis[510], Time[510], e[510][510], w[510][510], dispre[510],Timepre[510], weight[510],NodeNum[510];
    bool visit[510];
    vector<int> dispath, Timepath, temppath;
    int st, fin, minnode = inf;
    //下面两个函数将记录前驱节点的数组转换成逆序的序列放到vector
    void dfsdispath(int v) {
        dispath.push_back(v);
        if(v == st) return ;
        dfsdispath(dispre[v]);
    }
    void dfsTimepath(int v) {
        Timepath.push_back(v);
        if(v == st) return ;
        dfsTimepath(Timepre[v]);
    }
    int main() {
        fill(dis, dis + 510, inf);
        fill(Time, Time + 510, inf);
        fill(weight, weight + 510, inf);
        fill(e[0], e[0] + 510 * 510, inf);
        fill(w[0], w[0] + 510 * 510, inf);
        int n, m;
        scanf("%d %d", &n, &m);//地图中地点的个数和路路径的条数
        int a, b, flag, len, t;
        for(int i = 0; i < m; i++) {
            //道路路结点编号V1 道路路结点编号V2 是否单行线 道路长度 所需时间
            scanf("%d %d %d %d %d", &a, &b, &flag, &len, &t);
            e[a][b] = len;
            w[a][b] = t;
            if(flag != 1) {
                e[b][a] = len;
                w[b][a] = t;
            }
        }
        scanf("%d %d", &st, &fin);
        dis[st] = 0;
        for(int i = 0; i < n; i++)
            dispre[i] = i;
        for(int i = 0; i < n; i++) {
            int u = -1, minn = inf;
            for(int j = 0; j < n; j++) {
                if(visit[j] == false && dis[j] < minn) {
                    u = j;
                    minn = dis[j];
                }
            }
            if(u == -1) break;
            visit[u] = true;
            for(int v = 0; v < n; v++) {
                if(visit[v] == false && e[u][v] != inf) {
                    if(e[u][v] + dis[u] < dis[v]) {//求最短路径
                        dis[v] = e[u][v] + dis[u];
                        dispre[v] = u;//v的前驱是u
                        weight[v] = weight[u] + w[u][v];
                    } else if(e[u][v] + dis[u] == dis[v] && weight[v] > weight[u] + w[u][v]) {//如果相同求时间最短的那条
                        weight[v] = weight[u] + w[u][v];
                        dispre[v] = u;
                    }
                }
            }
        }
        dfsdispath(fin);
        Time[st] = 0;
        fill(visit, visit + 510, false);
        for(int i = 0; i < n; i++) {//求最快路径（如果相同求结点数最⼩的那条）
            int u = -1, minn = inf;
            for(int j = 0; j < n; j++) {
                if(visit[j] == false && minn > Time[j]) {
                    u = j;
                    minn = Time[j];
                }
            }
            if(u == -1) break;
            visit[u] = true;
            for(int v = 0; v < n; v++) {
                if(visit[v] == false && w[u][v] != inf) {
                    if(w[u][v] + Time[u] < Time[v]) {
                        Time[v] = w[u][v] + Time[u];
                        Timepre[v]=(u);
                        NodeNum[v]=NodeNum[u]+1;
                    } else if(w[u][v] + Time[u] == Time[v]&&NodeNum[u]+1<NodeNum[v]) {//如果相同求结点数最⼩的
                        Timepre[v]=(u);
                        NodeNum[v]=NodeNum[u]+1;
                    }
                }
            }
        }
        dfsTimepath(fin);
        printf("Distance = %d", dis[fin]);
        if(dispath == Timepath) {
            printf("; Time = %d: ", Time[fin]);
        } else {
            printf(": ");
            for(int i = dispath.size() - 1; i >= 0; i--) {
                printf("%d", dispath[i]);
                if(i != 0) printf(" -> ");
            }
            printf("\nTime = %d: ", Time[fin]);
        }
        for(int i = Timepath.size() - 1; i >= 0; i--) {
            printf("%d", Timepath[i]);
            if(i != 0) printf(" -> ");
        }
        return 0;
    }

### 1072. Gas Station (30) ###

[https://pintia.cn/problem-sets/994805342720868352/problems/994805396953219072][https_pintia.cn_problem-sets_994805342720868352_problems_994805396953219072]

这道题的背景开始让我挺困惑的，不过也能明白：

好比是我要给我的车加油，我会选最偏僻郊区（离居民区最近的人最远）但是还在我能到的范围内的一座加油站。

而且如果有多个相同距离的加油站，就选离我的邻居们平均最近的一个。

“离居民区最近的人最远”有两个最字，就是比较两次最值，第一次是加油站离居民区最近的距离，第二次是在第一次基础上，找最远距离的加油站。

第三个最字在“离我的邻居们平均最近”，这个和上面两个最字里一起统计。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70 1][]

#include <iostream>
    #include <algorithm>
    #include <string>
    using namespace std;
    const int inf = 999999999;
    int n, m, k, ds, station;
    int e[1020][1020], dis[1020]; 
    bool visit[1020];
    int main() {
        fill(e[0], e[0] + 1020 * 1020, inf);
        fill(dis, dis + 1020, inf);
        scanf("%d%d%d%d", &n, &m, &k, &ds);
        for(int i = 0; i < k; i++) {
            int tempdis;
            string s, t;
            cin >> s >> t >> tempdis;
            int a, b;
            if(s[0] == 'G') {
                s = s.substr(1);
                a = n + stoi(s);
            } else {
                a = stoi(s);
            }
            if(t[0] == 'G') {
                t = t.substr(1);
                b = n + stoi(t);
            } else {
                b = stoi(t);
            }
            e[a][b] = e[b][a] = tempdis;
        }
        int ansid = -1;
        double ansdis = -1, ansaver = inf;
        for(int index = n + 1; index <= n + m; index++) {//计算每个加油站到居民区每户人家的距离
            double mindis = inf, aver = 0;
            fill(dis, dis + 1020, inf);
            fill(visit, visit + 1020, false);
            dis[index] = 0;
            for(int i = 0; i < n + m; i++) {//计算每户居民或者加油站出发到别的点的最短路径，不要区别是居民还是加油站
                int u = -1, minn = inf;
                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];
                }
            }
            for(int i = 1; i <= n; i++) {//找出离该处加油站最近的居民
                if(dis[i] > ds) {
                    mindis = -1;
                    break;
                }
                if(dis[i] < mindis) mindis = dis[i];
                aver += 1.0 * dis[i];
            }
            if(mindis == -1) continue;
            aver = aver / n;
            if(mindis > ansdis) {//找出离最近的居民最远的加油站
                ansid = index;
                ansdis = mindis;
                ansaver = aver;
            } else if(mindis == ansdis && aver < ansaver) {
                ansid = index;
                ansaver = aver;
            }
        }
        if(ansid == -1)
            printf("No Solution");
        else
            printf("G%d\n%.1f %.1f", ansid - n, ansdis, ansaver);
        return 0;
    }

### 1003 Emergency (25分) ###

[https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376][https_pintia.cn_problem-sets_994805342720868352_problems_994805523835109376]

#include <iostream>
    #include <algorithm>
    using namespace std;
    int n, m, c1, c2;
    int e[510][510], weight[510], dis[510], num[510], w[510];
    bool visit[510];
    const int inf = 99999999;
    int main() {
        scanf("%d%d%d%d", &n, &m, &c1, &c2);
        for(int i = 0; i < n; i++)
            scanf("%d", &weight[i]);
        fill(e[0], e[0] + 510 * 510, inf);
        fill(dis, dis + 510, inf);
        int a, b, c;
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &a, &b, &c);
            e[a][b] = e[b][a] = c;
        }
        dis[c1] = 0;
        w[c1] = weight[c1];
        num[c1] = 1;
        for(int i = 0; i < n; i++) {
            int u = -1, minn = inf;
            for(int j = 0; j < n; j++) {
                if(visit[j] == false && dis[j] < minn) {
                    u = j;
                    minn = dis[j];
                }
            }
            if(u == -1) break;
            visit[u] = true;
            for(int v = 0; v < n; v++) {
                if(visit[v] == false && e[u][v] != inf) {
                    if(dis[u] + e[u][v] < dis[v]) {
                        dis[v] = dis[u] + e[u][v];
                        num[v] = num[u];
                        w[v] = w[u] + weight[v];
                    } else if(dis[u] + e[u][v] == dis[v]) {
                        num[v] = num[v] + num[u];
                        if(w[u] + weight[v] > w[v])
                            w[v] = w[u] + weight[v];
                    }
                }
            }
        }
        printf("%d %d", num[c2], w[c2]);
        return 0;
    }

[https_blog.csdn.net_allisonshing_article_details_100643092]: https://blog.csdn.net/allisonshing/article/details/100643092
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020070622070475.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw==,size_16,color_FFFFFF,t_70
[https_pintia.cn_problem-sets_994805342720868352_problems_994805358663417856]: https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856
[https_pintia.cn_problem-sets_994805342720868352_problems_994805396953219072]: https://pintia.cn/problem-sets/994805342720868352/problems/994805396953219072
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200706214447124.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw==,size_16,color_FFFFFF,t_70
[https_pintia.cn_problem-sets_994805342720868352_problems_994805523835109376]: https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376