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
输出占一行，第一个数是最小要消耗多少能量，第二个数是消耗这些能量最多获得多少价值的珠宝。两个数用空格分开
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;
}