PYA A_1003 Emergency

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805523835109376

解：
最短路径

1.迪杰斯特拉

#include <cstdio>
#include <climits>
#include <algorithm>

using namespace std;

const int maxn = 510;

int n, m, c1, c2;
int G[maxn][maxn];
int men[maxn];//存放点权，即救援队数
int num[maxn];//存放到每个点的最短路径数
int w[maxn];//存放可聚集的队伍数
int v[maxn];//存放最短路径长度
bool vis[maxn];//是否访问过

void DJS(int s)
{
    fill(v, v + n, INT_MAX);
    fill(num, num + n, 0);
    fill(w , w + n, 0);
    v[s] = 0;
    w[s] = men[s];
    num[s] = 1;

    for (int i = 0; i < n; i++)
    {   
        int u = -1, min = INT_MAX;

        for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
            if (!vis[i] && v[i] < min)  min = v[u = i];

        if (u == -1) return;//如果剩下的顶点与源点不通，返回

        vis[u] = true;

        for (int j = 0; j < n; j++)
        {
            if (vis[j] || G[u][j] == INT_MAX) continue;

            int t = v[u] + G[u][j];

            if (t < v[j])
            {
                v[j] = t;
                num[j] = num[u];
                w[j] = w[u] + men[j];
            }  
            else if (t == v[j])
            {
                num[j] += num[u];

                if (w[u] + men[j] > w[j]) w[j] = w[u] + men[j];
            }
        }
    }
}

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

    fill(G[0], G[0] + maxn * maxn, INT_MAX);

    for (int i = 0; i < n; i++)
        scanf("%d", men + i);

    while (m--)
    {
        int a, b, l;

        scanf("%d %d %d", &a, &b, &l);

        G[a][b] = G[b][a] = l;
    }

    DJS(c1);

    printf("%d %d", num[c2], w[c2]);

    return 0;
}

2.迪杰斯特拉 + DFS （模板）

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

using namespace std;

const int maxn = 510;

int n, m, c1, c2;
int G[maxn][maxn];
int weight[maxn];//存放点权，即救援队数
int d[maxn];//存放最短路径长度
bool vis[maxn];//是否访问过
vector<int> pre[maxn];//存放顶点在最短路径中的前驱

void DJS(int s)
{
    fill(d, d + n, INT_MAX);
    d[s] = 0;

    for (int i = 0; i < n; i++)
    {   
        int u = -1, min = INT_MAX;

        for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
            if (!vis[i] && d[i] < min)  min = d[u = i];

        if (u == -1) return;//如果剩下的顶点与源点不通，返回

        vis[u] = true;

        for (int v = 0; v < n; v++)
        {
            if (vis[v] || G[u][v] == INT_MAX) continue;

            int t = d[u] + G[u][v];

            if (t < d[v])
            {
                d[v] = t;
                pre[v].clear();
                pre[v].push_back(u);
            }  
            else if (t == d[v])
                pre[v].push_back(u);
        }
    }
}

int num = 0;//存放最短路径条数
int opt_w = 0;//存放最大点权和
vector<int> path;

void DFS(int v)
{
    if (v == c1)//递归边界，如果遍历到起点
    {
        path.push_back(v);

        num++;

        int val = 0;
        for (int i = path.size() - 1; i >= 0; i--)
            val += weight[path[i]];

        if (val > opt_w) opt_w = val;

        path.pop_back();

        return;
    }

    path.push_back(v);

    for (int i = 0; i < pre[v].size(); i++)
        DFS(pre[v][i]);

    path.pop_back();
}

int main(void) 
{
    scanf("%d %d %d %d", &n, &m, &c1, &c2);
    
    fill(G[0], G[0] + maxn * maxn, INT_MAX);

    for (int i = 0; i < n; i++)
        scanf("%d", weight + i);
    
    while (m--)
    {
        int a, b, l;
        scanf("%d %d %d", &a, &b, &l);

        G[a][b] = G[b][a] = l;
    }

    DJS(c1);
    DFS(c2);

    printf("%d %d", num, opt_w);

    return 0;
}

3.BF算法

#include <cstdio>
#include <climits>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int maxn = 510;

typedef struct node{
    int id, dis;

    node (int _id, int _dis) : id(_id), dis(_dis) {};
}Node;

int n, m, c1, c2;
int weight[maxn];//存放点权，即救援队数
int num[maxn];//存放到每个点的最短路径数
int w[maxn];//存放可聚集的队伍数
int d[maxn];//存放最短路径长度
vector<Node> adj[maxn];//邻接表
set<int> pre[maxn];//存放顶点在最短路径中的前驱

void BF(int s)
{
    fill(d, d + n, INT_MAX);
    memset(w, 0, sizeof(w));
    memset(num, 0, sizeof(num));

    w[s] = weight[s];
    d[s] = 0;
    num[s] = 1;

    for (int i = 0; i < n - 1; i++)
    {
        for (int u = 0; u < n; u++)
        {
            if (d[u] == INT_MAX) continue;

            for (int v = 0; v < adj[u].size(); v++)
            {
                int id = adj[u][v].id, dis = adj[u][v].dis;

                if (dis + d[u] < d[id])
                {
                    d[id] = dis + d[u];
                    num[id] = num[u];
                    w[id] = weight[id] + w[u];
                    pre[id].clear();
                    pre[id].insert(u);
                }
                else if (dis + d[u] == d[id])
                {
                    if (weight[id] + w[u] > w[id])
                        w[id] = weight[id] + w[u];

                    num[id] = 0;
                    
                    pre[id].insert(u);
                    for (set<int>::iterator it = pre[id].begin(); it != pre[id].end(); ++it)
                        num[id] += num[*it];
                }
            }
        }
    }
}

int main(void) 
{
    // freopen("input.txt", "r", stdin);
    scanf("%d %d %d %d", &n, &m, &c1, &c2);

    for (int i = 0; i < n; i++)
        scanf("%d", weight + i);
    
    while (m--)
    {
        int a, b, l;
        scanf("%d %d %d", &a, &b, &l);

        adj[a].push_back(node(b, l));
        adj[b].push_back(node(a, l));
    }

    BF(c1);

    printf("%d %d", num[c2], w[c2]);

    return 0;
}