1003 Emergency

单源正权最短路径大小和计数

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input Specification:

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) – the number of cities (and the cities are numbered from 0 to N−1), M – the number of roads, C​1​​ and C​2​​ – the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c​1​​, c​2​​ and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C​1​​ to C​2​​.

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C​1​​ and C​2​​, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

Sample Input:

5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output:

2 4

本题包括三个小题,分别为无环正权无向图单源最短路权、最短路统计以及最大点权。
首先,正权单源最短路问题优先想到的是dijkstra算法(floyd算每两点最短路,prim算生成树),本题显然是对dijkstra算法进行改造。

输入格式第一行是点数,边数,源点,目标点。
第二行是每个城市的点权。
接下来就是每个边的边权。

值得注意的点是,有可能存在源点等于目标点的情况,这种特例需要想清楚。

题解如下:

#include <cstdio>
#include <iostream>
#define MAXN 501         // 最大城市数
#define INFINITY 1000000 // 无穷大
using namespace std;
int map[MAXN][MAXN]; // 邻接矩阵,在算这种最短路径的题时千万不要更改原数据!!!!!
int dis[MAXN];       // 某个点到源点的距离
int wayn[MAXN];      // 从源点到某个点的最短路径条数
int sumn[MAXN];      // 从源点到某个点的所有最短路径下的最大点权和
bool vis[MAXN];      // dijkstra算法里用于判断一个点是否被“敲定”的数组
int cityN, roadN;    // 算法体里这种都要用到的变量写成全局变量就很爽,不需要初始化0
int st, ed;
int city[MAXN]; // 每个城市的点权

void dijkstra()
{
    for (int i = 0; i < cityN; i++) // cityN个轮次,每一轮都将未访问且离源点最近的点“敲定”下来,然后对图进行一次松弛,
    {
        // 找本轮次离源点距离最小的点并将其敲定下来
        int n = -1; // n用于保存当前轮次离源点最近的点
        int min = INFINITY;
        for (int j = 0; j < cityN; j++)
        {
            if (vis[j] == false && dis[j] < min)
            {
                n = j;
                min = dis[j];
            }
        }

        if (n == -1)
        {
            return; // 如果找不到,那说明已经遍历所有与源点有路线连接的点,可以直接跳出
        }

        vis[n] = true;
        // 最小点n敲定完毕
        // 下面开始对图进行松弛
        for (int j = 0; j < cityN; j++) // 对于n的邻接点j进行松弛
        {
            if (vis[j] == true || map[n][j] == INFINITY)
            {
                // 1. 如果j已经被敲定,就直接跳过,防止来回松弛
                // 2. 保证n和j是邻接的,不邻接的话也跳过(这个时候就体现出不要更改原数据的重要性了
                continue;
            }

            if (dis[j] > dis[n] + map[n][j]) // 对于点j,如果从源点出发经过n拐到j的路径长度比当前记录的从源点到j的最短路径还要短,则进行一次松弛
            {
                dis[j] = dis[n] + map[n][j]; // 更新点j的最短路径长度
                sumn[j] = sumn[n] + city[j]; // 因为更新了最短路径,所以无条件更新当前的“最大点权和”
                wayn[j] = wayn[n];           // 注意这里!!!,当最短路有更新的时候要更新最短路径条数,原因同上,这点之前没有想清楚
            }
            else if (dis[j] == dis[n] + map[n][j]) // 如果点n恰好满足左式,说明要有一条经过n的路径能够满足当前记录的最短路径的要求
                                                   // 此时不必进行松弛,但是仍需要更新最短路径条数和最大点权和
            {
                wayn[j] += wayn[n];              // 源点到j的最短路径条数是到所有满足“与j邻接+处于最短路径中”的n的最短路径条数的和(思路的重难点)
                if (sumn[j] < sumn[n] + city[j]) // 如果有更大的点权和则将其更新
                {
                    sumn[j] = sumn[n] + city[j];
                }
            }
        }
    }
}

int main()
{
    cin >> cityN >> roadN;
    cin >> st >> ed;
    for (int i = 0; i < cityN; i++)
    {
        int value;
        cin >> value;
        city[i] = value;
    }
    //邻接矩阵,比较好建,不多说
    for (int i = 0; i < cityN; i++)
    {
        for (int j = 0; j < cityN; j++)
        {
            map[i][j] = INFINITY;
        }
    }
    for (int i = 0; i < cityN; i++)
    {
        map[i][i] = 0;
    }
    for (int i = 0; i < roadN; i++)
    {
        int s, e, c;
        cin >> s >> e >> c;
        map[s][e] = c;
        map[e][s] = c;
    }
    //邻接矩阵建立完毕

    // 其他变量的初始化也很重要,不要忘记
    for (int i = 0; i < cityN; i++)
    {
        dis[i] = map[st][i];
    }
    wayn[st] = 1;
    sumn[st] = city[st];
    dijkstra();
    // cout << wayn[ed] << " " << sumn[ed];
    for (int i = 0; i < cityN; i++)
    {
        cout << i << ". dis:" << dis[i] << " wayn:" << wayn[i] << " sumn:" << sumn[i] << "\n";
    }

    return 0;
}

总结

有关图的最短路径这里有一篇不错的博文:https://segmentfault.com/a/1190000023280254

里面有提到,这些算法的重点在于确定“松弛顺序”,以保证被松弛过的点尽量少再被松弛。每次松弛都是一个比较近的路径代替比较远的路径的过程,如果我们能够首先“敲定”所有比较近的路径,即保证去松弛别的点的点不会被再松弛,那么就可以使复杂度最小化。决定边的松弛顺序主要取决于图的性质(有环无环)(有无负权重边)。


所以在做题时:

  1. 当权值为非负且只需要单源时,用Dijkstra。
  2. 当权值有负值,且没有负圈,则用SPFA,SPFA能检测负圈,但是不能输出负圈。
  3. 当权值有负值,而且可能存在负圈,则用SPFA,能够检测并输出负圈,当存在一个点入队大于等于V次时说明存在负圈。
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments