题意：给定起点和终点，每个点都有价值，给出m条双向边和边的权值，可能会有重边。

求解：从起点到终点的路径数，走过的点能拿到的最大价值，以及输出那条能拿到最大价值的边。

本题主要是需要进行两次最短路，第一次为了算出从起点到任意点的最短距离。第二次最短路根据第一次最短路算出来的最短距离，可以算出从起点到任意点的能拿到的最大价值，还有路径总数。在松弛这些点的时候可以将路径保存下来。递归输出即可。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#define inf 10000000#define eps 1e-8#define G 9.8const int Max = 509;int dis[Max], pre[Max], mat[Max][Max], giv[Max], vul[Max], sp[Max];bool vis[Max];int n;void dij2(int u) { memset(vis,0,sizeof(vis)); giv[u] = vul[u]; pre[u] = -1; int ans ,p ; while(1) { ans = inf; p = -1; for( int i=0;i
             
               dis[i] && !vis[i]) { ans = dis[i]; p = i; } } if(p == -1) break; vis[p] = 1; for( int i=0;i
              
                dis[i] && !vis[i]) { ans = dis[i]; p = i; } } if(p == -1) break; vis[p] = 1; for( int i=0;i
               
                 dis[p] + mat[p][i]) { dis[i] = dis[p] + mat[p][i] ; } } }}int main() { int m ,s ,e ; while (scanf("%d%d%d%d",&n ,&m ,&s, &e) == 4) { memset(sp,0,sizeof(sp)); memset(giv,0,sizeof(giv)); for (int i = 0;i < n; i++) { for (int j = 0;j < n; j++) { mat[i][j] = inf; } } for (int i = 0;i < n; i++) scanf("%d",&vul[i]); for (int i = 0;i < m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(c < mat[a][b]) mat[a][b] = mat[b][a] = c; } for(int i=0;i
                
                 0;i--) { printf("%d ",ans[i]); } printf("%d\n",ans[0]); } return 0;}