题意：

就是给你一张图， 求一点到另外一点的花费最短时间的路径，如果存在多条，那么选取其中的价值最大的那一条

简单的搜索题，直接附代码

#include<stdio.h>
#define MAXVER 501
#define MAXEDG 12501
typedef struct{
  int vex[MAXVER];//teams in every city
  int arc[MAXVER][MAXVER];//length of road
  int N, M;
}Mgraph;

Mgraph g;
int visited[MAXVER], c1, c2, count, max, min = 66235;

void read(){
  int i, j, r, c;
  scanf("%d%d%d%d", &(g.N), &(g.M), &c1, &c2);
  for(i = 0; i < g.N; i++)//the number of teams in i city
    scanf("%d", &g.vex[i]);
  for(i = 0; i < MAXVER; i++)//init, make every roads be 0
    for(j = 0; j < MAXVER; j++){
      g.arc[i][j] = 0;
    }
    for(i = 0; i < g.M; i++){//length of the road
      scanf("%d%d%d", &r, &c, &j);
      g.arc[r][c] = g.arc[c][r] = j;    
    }
}

void dfs(int now, int right, int team)
{
  int i;
  if(right > min)
    return;
  if(now == c2)
  {
    if(right == min){
      count ++;
      if(team >= max)
        max = team;
    }
    if(right < min){
      min = right;
      count = 1;
      max = team;
    }
    return ;
  }
  for(i = 0; i < g.N; i++){
    if(!visited[i] && g.arc[now][i] > 0)  {
      visited[i] = 1;
      dfs(i, right + g.arc[now][i], team + g.vex[i]);
      visited[i] = 0;
    }
  }
}

int main(){

  //freopen("in.txt", "r", stdin);
  read();
//  if(c1 == c2)
//    printf("1 g.vex[c1]");
//  else{
    visited[c1] = 1;
    dfs(c1, 0, g.vex[c1]);
    printf("%d %d", count, max); 
//  }
  return 0;
}

pat 1003