Let‘s play computer game（最短路 + dfs找出所有确定长度的最短路）

Let‘s play computer game

Description

xxxxxxxxx在疫情期间迷上了一款游戏，这个游戏一共有nnn个地点（编号为1——n1——n1——n），他每次从一个地点移动到另外一个地点需要消耗

一定的能量，每一个地点都有一些珠宝，输入中会把每一个地方的珠宝价值估算成一个值。

xxxxxxxxx想请聪明的你帮他找出来从编号为sss的地点，到编号为ddd的地点最小要消耗多少能量，消耗这些能量最多获得多少价值的珠宝

Input

第一行输入n，s，dn，s，dn，s，d。其意义如上描述（n<520n<520n<520）

第二行有nnn个数XiX_iXi，比如i==1i==1i==1描述编号为1的点有珠宝价值为XiX_iXi（这里保证XiX_iXi大于等于0） (Xi<1000X_i<1000Xi<1000)

下面输入一个n∗nn*nn∗n的矩阵，比如第iii行，第j列的值为xxx，就表示从编号为iii到编号为jjj的地方距离为x (x<1000)x (x<1000)x (x<1000)（这里保证xxx大于等于0）

注意：这是一个单向路，即从编号为iii到编号为jjj的距离可能不等于从编号为jjj到编号为iii

Output

输出占一行，第一个数是最小要消耗多少能量，第二个数是消耗这些能量最多获得多少价值的珠宝。两个数用空格分开

Sample Input 1

4 1 4

20 30 40 10

0 1 2 3

999 0 999 2

999 999 0 2

999 999 999 0

Sample Output 1

3 60

Sample Input 2

7 2 3

341 527 189 740 490 388 989

0 489 711 174 305 844 971

492 0 998 954 832 442 424

619 906 0 154 293 395 439

735 738 915 0 453 748 786

550 871 932 693 0 326 53

904 732 835 354 364 0 691

669 157 719 282 875 573 0

Sample Output 2

998 716

Hint

第一个样例解释：

解释：

把这个矩阵翻译成边

1->2 1

2->4 2

1->4 3

1->3 2

3->4 2

正确路径：1->2->4

后面的就不用说了吧^_^

Source

qmh

思路

题意：一个人从 s出发到点e，在所给的图中每个点就有个一个珠宝（价值会给我们的），在消耗能量最少（即：最短路）的基础上求出能得到最大珠宝总价值是多少

思路：先用 Dijkstra 或者 Spfa 来求一下从 s -> e 的最短路的距离，有了这个最短距离之后，那么我们可以用 dfs 去深搜没一条路径，找到在所有符合最短路的路径中价值最大的那条的价值，

注意：我们在dfs的时候是可以做优化的，让我们来看看代码中的这一段 dis[i] == dis[j] + Grf[j][i] ， dis表示的是从 s 点出发到 i 点的最短距离 Grf 是存图的临接矩阵，如果上述的等式不成立，那么我们我们就可以不用往下递归了，因为当前走的这条路已经不可能在符合题意了，解释：假设又一条路：s -> 1 -> j -> i -> 3 -> e. | Grf[j][i] 表示从j 到 i 的距离，如果从s 点出发到 i的距离不等于从s出发到 dis[i] 的最短路的距离，那么它一定不可能是我们所找的最短路径，，，自己在思考思考吧

代码

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

#define INF 0x3f3f3f3f

const int Len = 550;

int Grf[Len][Len];

int dis[Len];

int n, s, e;

int val[Len];

int Dijkstra(int s, int e)

{

    int vis[Len];

    for(int i = 1; i <= n; i ++)

        vis[i] = 0, dis[i] = Grf[s][i];

    vis[s] = 1;

    for(int i = 1; i <= n; i ++)

    {

        int mn = INF;

        for(int i = 1; i <= n; i ++)        //1. 在这个集合中选择与该集合相连的最小权值的那条边的点

        {

            if(! vis[i] && dis[i] < mn)

            {

                mn = dis[i];

                s = i;

            }

        }

        //2. 把新加入的这个点做上标记

        vis[s] = 1;

        //3. 更新与这个点相连的边的点 dis 距离（因为在集合中的距离已经确定是最短距离，而我们在新加入这个点之后，我们可以更新与这个点相连的点（这个点是在集合外的点）的最短距离）

        for(int i = 1; i <= n; i ++)

            if(dis[s] + Grf[s][i] < dis[i])

                dis[i] = dis[s] + Grf[s][i];

    }

    return dis[e];

}

int res = -1;

int mrk[Len];

void dfs(int mn_dis, int pri, int s, int e)

{

    if(s == e)

    {

        if(res < pri)

            res = pri;

        return;

    }

    for(int i = 1; i <= n; i ++)

    {

        if(! mrk[i] && dis[i] == dis[s] + Grf[s][i])    //这里的 dis[i] == dis[s] + Grf[s][i] 优化避免了盲目 搜索所有路径，假设有一条路径：s -> 2 -> 3 -> e , 如果dis[3] 不等于我们dfs过程到节点3的路径长度，那么就算dfs递归到了终点，这条路径的长度也绝对不可能等于dis[e]

        {

            mrk[i] = 1;

            dfs(mn_dis, pri + val[i], i, e);

            mrk[i] = 0;

        }

    }

}

int main()

{

    //freopen("A.txt","r",stdin);

    int tem;

    scanf("%d %d %d", &n, &s, &e);

    for(int i = 1; i <= n; i ++)

        scanf("%d", &val[i]);

    for(int i = 1; i <= n; i ++)

        for(int j = 1; j <= n; j ++)

            scanf("%d", &tem), Grf[i][j] = tem;

    int mn_dis = Dijkstra(s, e);

    dfs(mn_dis, 0, s, e);

    printf("%d %d\n", dis[e], res);

    return 0;

}

巴特西

Let‘s play computer game（最短路 + dfs找出所有确定长度的最短路）

思路

代码

最新文章

热门文章