解法一：DFS

  1. import java.io.*;
  2. import java.util.*;
  4. public class Main {
  6.     private static int capacity, N, target, M;
  7.     private static int[][] map;
  8.     private static final int INF = 0x3f3f3f3f;
  9.     private static boolean[] isVisited;
  10.     private static int[] bikes;
  11.     private static int minTime, minSend, minBack;
  12.     private static List<Integer> path;
  14.     public static void main(String[] args) throws IOException {
  15.         StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  16.         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  17.         in.nextToken();
  18.         capacity = (int) in.nval;
  19.         in.nextToken();
  20.         N = (int) in.nval + 1;
  21.         in.nextToken();
  22.         target = (int) in.nval;
  23.         in.nextToken();
  24.         M = (int) in.nval;
  26.         map = new int[N][N];
  27.         for (int[] arr : map) {
  28.             Arrays.fill(arr, INF);
  29.         }
  31.         bikes = new int[N];
  32.         for (int i = 1; i < N; ++i) {
  33.             in.nextToken();
  34.             bikes[i] = (int) in.nval;
  35.         }
  37.         int u, v, val;
  38.         while (M-- > 0) {
  39.             in.nextToken();
  40.             u = (int) in.nval;
  41.             in.nextToken();
  42.             v = (int) in.nval;
  43.             in.nextToken();
  44.             val = (int) in.nval;
  45.             map[u][v] = val;
  46.             map[v][u] = val;
  47.         }
  49.         isVisited = new boolean[N];
  50.         Arrays.fill(isVisited, false);
  51.         isVisited[0] = true;
  52.         minBack = minSend = minTime = INF;
  53.         path = new ArrayList<>();
  54.         List<Integer> cities = new LinkedList<>();
  55.         cities.add(0);
  56.         dfs(0, 0, cities);
  58.         out.print(minSend);
  59.         out.print(" " + path.get(0));
  60.         for (int i = 1; i < path.size(); ++i) {
  61.             out.print("->" + path.get(i));
  62.         }
  63.         out.println(" " + minBack);
  64.         out.flush();
  65.     }
  67.     private static void dfs(int index, int time, List<Integer> cities) {
  68.         // 剪枝
  69.         if (time > minTime) {
  70.             return;
  71.         }
  72.         if (index == target) {
  73.             int send = 0;
  74.             int bikeSum = 0;
  75.             for (int i = 1; i < cities.size(); ++i) {
  76.                 bikeSum += bikes[cities.get(i)];
  77.                 send = Math.max(send, i * capacity / 2 - bikeSum);
  78.             }
  79.             int back = Math.max(send + bikeSum - (cities.size() - 1) * capacity / 2,0);
  80.             if (time < minTime || send < minSend || send == minSend && back < minBack) {
  81.                 path.clear();
  82.                 path.addAll(cities);
  83.                 minTime = time;
  84.                 minSend = send;
  85.                 minBack = back;
  86.             }
  87.         } else {
  88.             for (int i = 1; i < N; ++i) {
  89.                 if (isVisited[i] || map[index][i] == INF) {
  90.                     continue;
  91.                 }
  92.                 isVisited[i] = true;
  93.                 cities.add(i);
  94.                 dfs(i, time + map[index][i], cities);
  95.                 cities.remove(cities.size() - 1);
  96.                 isVisited[i] = false;
  97.             }
  98.         }
  99.     }
  100. }