PAT-A-1003

所有甲级题全解

原题链接

生僻词汇

scattered 分散的

题意

你是个救援队头子，要从 A 到 B 点去救人，路途城市的人手可以捎上，求最短路径数量，跟最短路情况下最多救援队人数

知识点

图的最短路径问题

多路径的第二权计算

思路

非负权最短路显然用 Dijkstra 算法

多解用 vector 储存

计算比较第二权，即点权：人手

代码

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
const int maxN = 501;
const int INF = 0x3fffffff;
int n, m, c1, c2, p1, p2, l, minDis = INF, maxPeo = 0, numOfDis = 0;
int G[maxN][maxN], w[maxN], d[maxN];
bool vis[maxN] = {false};
vector<int> pre[maxN];
vector<int> tmp;

void Dij(int c) {
    //重置距离
    fill(d, d + maxN, INF);
    d[c] = 0;

    //找最近的结点 n 次
    for (int i = 0; i < n; i++) {
        //找下一个最近的结点 u
        int u = -1, Min = INF;
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && d[v] < Min) {
                u = v;
                Min = d[v];
            }
        }

        //未找到最近结点 u
        if (u == -1) return;

        //访问 u
        vis[u] = true;

        //尝试更新最短距离 u -> v
        for (int v = 0; v < n; v++) {
            //未访问，可访问
            if (vis[v] == false && G[u][v] != INF) {
                //路径相等
                if (d[u] + G[u][v] == d[v]) {
                    //更新前驱结点
                    pre[v].push_back(u);
                }
                    //路径更短，更新
                else if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
            }
        }
    }
}

void DFS(int v) {
    //边界条件
    if (v == c1) {
        tmp.push_back(v);
        int dis = 0, peo = 0;

        //计算路径 - 边权
        for (int i = 0; i < tmp.size() - 1; i++) {
            int u1 = tmp[i], u2 = tmp[i + 1];
            dis += G[u1][u2];
        }

        //计算人数 - 点权
        for (int i = 0; i < tmp.size(); i++) {
            int u = tmp[i];
            peo += w[u];
        }

        //若为最短路径
        if (dis < minDis) {
            numOfDis = 1;
            minDis = dis;
            maxPeo = peo;
        }

            //若最短路径不唯一
        else if (dis == minDis) {
            numOfDis++;
            if (peo > maxPeo) maxPeo = peo;
        }
        tmp.pop_back();
    }

    //递归式
    tmp.push_back(v);
    for (int i = 0; i < pre[v].size(); i++) {
        DFS(pre[v][i]);
    }
    tmp.pop_back();
}

int main() {
    //输入
    scanf("%d%d%d%d", &n, &m, &c1, &c2);

    //点权赋值
    for (int i = 0; i < n; ++i) {
        scanf("%d", &w[i]);
    }

    //关闭图
    fill(G[0], G[0] + maxN * maxN, INF);

    //边权赋值
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &p1, &p2, &l);
        G[p1][p2] = G[p2][p1] = l;
    }

    Dij(c1);
    DFS(c2);
    printf("%d %d", numOfDis, maxPeo);
    return 0;
}