PTA 1003 Emergency (25 分)（详细翻译+注释）

我会带着你远行 2022-09-03 01:27 240阅读 0赞

# 背景： #

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.

**作为一个城市的紧急救援队队长，你会得到一张你所在国家的特殊地图。这张地图显示了几个被一些道路连接的分散的城市。每个城市的救援队伍数量和任何一对城市之间的每条道路的长度都被标记在地图上。当有一个紧急电话从其他城市给你，你的工作是尽快带领你的该城市的全部救援队从这个城市赶到那个城市，同时，召集途径城市的全部救援队。**

# 输入格式： #

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, C1 and C2 - 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 c1 , c2 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 C1 to C2 .

**每个输入文件包含一个测试用例。对于每个测试用例，第一行包含4个正整数：N(≤500)代表城市的数量(城市编号从0到N−1)，M 代表道路的数量，C 1和C 2 分别代表你目前所在的城市的编号和你要去拯救的城市的编号。下一行包含N个整数，第i个整数是第i个城市的救援队数量。接下来是M行数，每行用三个整数c 1, c 2和 L 来描述一条道路，c 1,和c 2表示一对城市，L表示这一对城市之间的道路的距离。本题保证从C 1到C 2至少存在一条路径。**

# 输出格式： #

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2 , 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.

**对于每个测试用例，在一行中打印两个数字：第一个数字是C 1和C 2之间不同的最短路径的数量，第二个数字是您在走最短路径的前提下可能召集到的救援团队的最大数量。一行中的两个数字必须用一个空格隔开，并且在第二个数字的末尾不允许有额外的空格。**

# 输入样例： #

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

# 输出样例： #

2 4

# 思路1： #

使用`图的深度优先遍历`两次完成求解。第一次求出最短路径的具体值，第二次求出答案。

## C实现代码： ##

#include <stdio.h>
    
    int book[500],mem[500],map[500][500],min = 99999999,num,m,n,a,b,sum1,sum2;
    //定义标记数组、救援队数量数组、存图二维数组、最短路径值、救援队数
    //城镇数、道路数、起点标号、终点标号、结果1、结果2
    
    void dfs1(int cur,int dis)//求最短路径值的函数（当前城市标号，当前行进距离）
    { 
        if(dis > min)//如果路程已经超过了当前的路程最小值
            return ;//因为距离过长而退回（为了减少运行时间）
        if(cur == b)//如果已经到达目标城市
        { 
            if(dis < min)//如果是全新的最短记录
                min = dis;//更新最短路径
            return ;//因为到达终点而退回
        }
        for(int i = 0;i < m;i++)//如果没有因为路程超标退出也没有到达目标城市，尝试走向下一个城镇
            if(map[cur][i] != 99999999 && book[i] == 0)//如果当前位置与下个城镇之间有路并且没有走过
            { 
                book[i] = 1;//标记这个城镇使之显示走过
                dfs1(i,dis + map[cur][i]);//前往下一个城镇
                book[i] = 0;//退回了，所以抹掉这个城镇的标记
            }
        return ;//因为无路可走而退回
    }
    
    void dfs2(int cur,int dis)//求出最终答案的函数（当前城市标号，当前行进距离）
    { 
        num += mem[cur];//进入一个城镇就要加上这个城镇的救援队数
        if(dis > min)//如果路程已经超过了上个函数求出的路程最小值
        { 
            num -= mem[cur];//退出一个城镇就要减掉这个城镇的救援队数
            return ;//因为距离过长而退回
        }
        if(cur == b)//如果已经到达目标城市（经过上一步的过滤，此时必然是以最短路径到达）
        { 
            sum1++;//最短路径数加1
            if(num >= sum2)//如果这是最大的救援队数
                sum2 = num;//更新答案
            num -= mem[cur];//退出一个城镇就要减掉这个城镇的救援队数
            return ;//因为到达终点而退回
        }
        for(int i = 0;i < m;i++)//如果没有因为路程超标退出也没有到达目标城市，尝试走向下一个城镇
            if(map[cur][i] != 99999999 && book[i] == 0)//如果当前位置与下个城镇之间有路并且没有走过
            { 
                book[i] = 1;//标记这个城镇使之显示走过
                dfs2(i,dis + map[cur][i]);//前往下一个城镇
                book[i] = 0;//退回了，所以抹掉这个城镇的标记
            }
        num -= mem[cur];//退出一个城镇就要减掉这个城镇的救援队数
        return ;//因为无路可走而退出
    }
    
    int main()
    { 
        scanf("%d %d %d %d",&m,&n,&a,&b);//输入城镇数、道路数、起点标号、终点标号
        for(int i = 0;i < m;i++)//读入每个城市的救援队数量
            scanf("%d",&mem[i]);
        for(int i = 0;i < m;i++)//初始化存图二维数组
            for(int j = 0;j < m;j++)
                if(i != j)
                    map[i][j] = 99999999;
        for(int i = 0;i < n;i++)//读入每个城市间的道路
        { 
            int c,d,e;
            scanf("%d %d %d",&c,&d,&e);
            map[c][d] = e;
            map[d][c] = e;//因为是无向图所以加这一行
        }
        book[a] = 1;//从a号城市为起点出发，所以将其标记
        dfs1(a,0);//进入函数1，求最短路径值
        dfs2(a,0);//进入函数2，求出答案
        printf("%d %d",sum1,sum2);//输出结果
        return 0;
    }

# 思路2： #

先使用一次`dijkstra`求出最短路径值。再使用一次`图的深度优先遍历`求出答案。

## C实现代码： ##

#include <stdio.h>
    
    int book[510],mem[510],map[510][510],dist[510];
    //定义标记数组、救援队数量数组、存图二维数组、与a点最短距离数组
    int max = 99999999,min,num,m,n,a,b,sum1,sum2;
    //最大值、最短路径值、救援队数、城镇数、道路数、起点标号、终点标号、结果1、结果2
    
    void dijkstra()
    { 
        int u;//定义一个储存最近点号码的变量
        for(int i = 0; i < m - 1; i++)//遍历a点所有可能的的相邻点
        { 
            min = max;//给min赋最大值
            for(int j = 0; j < m; j++)//试图找到所有相邻点里没走过的最近的一个
            { 
                if(book[j] == 0 && dist[j] < min)//如果找到
                { 
                    min = dist[j];//更新最短路径值
                    u = j;
                }
            }
            book[u] = 1;//标记这个点
            for(int k = 0; k < m; k++) //遍历这个点到全部其他点的距离（map[u][k]）
            	//如果u到k有路可走并且a点到k点的距离大于a点到u点的距离于u点到k点的距离之和
                if((map[u][k] != max) && (dist[k] > (dist[u] + map[u][k])))
                    dist[k] = dist[u] + map[u][k];//更新最短距离数组
        }
        min = dist[b];//a到b的最短路径赋值给min
    }
    
    void dfs(int cur,int dis)//求出最终答案的函数（当前城市标号，当前行进距离）
    { 
        num += mem[cur];//进入一个城镇就要加上这个城镇的救援队数
        if(dis > min)//如果路程已经超过了上个函数求出的路程最小值
        { 
            num -= mem[cur];//退出一个城镇就要减掉这个城镇的救援队数
            return ;//因为距离过长而退回
        }
        if(cur == b)//如果已经到达目标城市（经过上一步的过滤，此时必然是以最短路径到达）
        { 
            sum1++;//最短路径数加1
            if(num >= sum2)//如果这是最大的救援队数
                sum2 = num;//更新答案
            num -= mem[cur];//退出一个城镇就要减掉这个城镇的救援队数
            return ;//因为到达终点而退回
        }
        for(int i = 0; i < m; i++)//如果没有因为路程超标退出也没有到达目标城市，尝试走向下一个城镇
            if(map[cur][i] != max && book[i] == 0)//如果当前位置与下个城镇之间有路并且没有走过
            { 
                book[i] = 1;//标记这个城镇使之显示走过
                dfs(i,dis + map[cur][i]);//前往下一个城镇
                book[i] = 0;//退回了，所以抹掉这个城镇的标记
            }
        num -= mem[cur];//退出一个城镇就要减掉这个城镇的救援队数
        return ;//因为无路可走而退出
    }
    
    int main()
    { 
        scanf("%d %d %d %d",&m,&n,&a,&b);//输入城镇数、道路数、起点标号、终点标号
        for(int i = 0; i < m; i++)//读入每个城市的救援队数量
            scanf("%d",&mem[i]);
        for(int i = 0; i < m; i++)
            for(int j = 0; j < m; j++)//初始化存图二维数组
                if(i != j)
                    map[i][j] = max;
        for(int i = 0; i < n; i++)//读入每个城市间的道路
        { 
            int c,d,e;
            scanf("%d %d %d",&c,&d,&e);
            map[c][d] = e;
            map[d][c] = e;//因为是无向图所以加这一行
        }
        for(int i = 0; i < n; i++)//初始化dist数组
            dist[i] = map[a][i];
        book[a] = 1;//从a号城市为起点出发，所以将其标记
        dijkstra();//进入dijkstra函数求出最短路径
        for(int i = 0; i < m; i++)//重置标记数组
            book[i] = 0;
        book[a] = 1;//从a号城市为起点出发，所以将其标记
        dfs(a,0);//进入深度优先遍历函数，求出答案
        printf("%d %d",sum1,sum2);//输出结果
        return 0;
    }

# 疑问： #

方法2时数组大小必须大于等于510否则会越界，而方法1只需要500就行，望读者告知原因。