你来到一个迷宫前。该迷宫由若干个房间组成，每个房间都有一个得分，第一次进入这个房间，你就可以得到这个分数。还有若干双向道路连结这些房间，你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定了你的起点和终点房间，你首要目标是从起点尽快到达终点，在满足首要目标的前提下，使得你的得分总和尽可能大。现在问题来了，给定房间、道路、分数、起点和终点等全部信息，你能计算在尽快离开迷宫的前提下，你的最大得分是多少么？
Input
第一行4个整数n (<=500), m, start, end。n表示房间的个数，房间编号从0到(n - 1)，m表示道路数,任意两个房间之间最多只有一条道路，start和end表示起点和终点房间的编号。
第二行包含n个空格分隔的正整数(不超过600)，表示进入每个房间你的得分。
再接下来m行，每行3个空格分隔的整数x, y, z (0<z<=200)表示道路,表示从房间x到房间y(双向)的道路,注意，最多只有一条道路连结两个房间, 你需要的时间为z。
输入保证从start到end至少有一条路径。
Output
一行，两个空格分隔的整数，第一个表示你最少需要的时间，第二个表示你在最少时间前提下可以获得的最大得分。
Input示例
3 2 0 2
1 2 3
0 1 10
1 2 11
Output示例
21 6
那这个题目，暴力的想法是求出所有最短路，选一条价值最大的
那其实不必这么麻烦，我们可以先求出一条最短路，同时更新其价值，如果存在比其价值更高并且还在这条最短路上的边
我们就继续让大的价值松弛小的价值，当然前提是在最短路上跑，于是有两种入队情况，第一距离被松弛，第二最短路的价值被松弛
那么之前我对dij的堆实现是有一些疑问的，怎么做到push进去的点按照权值优先级pop呢，因为你push进去那个值是死的
而dist数组是动态变化的，难道我们要动态修改堆吗，这就很复杂了
那其实不必这样，初始我们只push需要松弛其他点的点就好，那么如果该点没松弛其他点之前被松弛怎么办，更新堆吗
那其实不必这样做，我们push一个dist更小的同样编号的点就好，第一他会先出来，如果终点被完全松弛，那么退出
如果权值大的也出来，那么它对于松弛过的边无能为力，所以综合一下，我们只是多花费了一些空间，但是由于dij的特性
队列中的点很有限，所以我们也不必担心空间上不足
附上代码
1 #include <stdio.h>
2 #include <queue>
3 #include <algorithm>
4 #include <vector>
5 using namespace std;
6 const int maxn=5e2+7;
7 struct node{
8 int v,a;node(){};node(int v,int a):v(v),a(a){};
9 bool operator < (const node &rhs) const{
10 return a>rhs.a;
11 }
12 };
13 vector<int> G[maxn];
14 const int INF=(~1u)>>2;
15 int dist[maxn],mon[maxn],p[maxn],s,e,n,m,w[maxn][maxn];
16 void dij(){
17 for(int i=0;i<n;++i) dist[i]=INF,mon[i]=0;
18 dist[s]=0;mon[s]=p[s];
19 priority_queue<node> Q;Q.push(node(s,0));
20 while(Q.size()){
21 node now=Q.top();Q.pop();
22 if(now.v==e) break;
23 for(int i=0;i<G[now.v].size();++i){
24 int v=G[now.v][i];
25 if(dist[v]>dist[now.v]+w[now.v][v]){
26 dist[v]=dist[now.v]+w[now.v][v];
27 mon[v]=p[v]+mon[now.v];
28 Q.push(node(v,dist[v]));
29 }
30 else if(dist[v]==dist[now.v]+w[now.v][v]){
31 if(mon[v]<p[v]+mon[now.v]){
32 mon[v]=p[v]+mon[now.v];
33 Q.push(node(v,dist[v]));
34 }
35 }
36 }
37 }
38 }
39 int main(){
40 //freopen("1459.txt","r",stdin);
41 scanf("%d%d%d%d",&n,&m,&s,&e);
42 for(int i=0;i<n;++i) scanf("%d",p+i);
43 int u,v,b;
44 for(int i=0;i<m;++i){
45 scanf("%d%d%d",&u,&v,&b);
46 G[u].push_back(v);
47 G[v].push_back(u);
48 w[u][v]=w[v][u]=b;
49 }dij();
50 printf("%d %d\n",dist[e],mon[e]);
51 return 0;
52 }