查询有1000个，所以先把各个救护点到各个点的最短路径保存下来，pre加一维就可以了，然后就是查询，一个点，对救护车数量不为0的点DFS，找出，符合的路径，然后救护车减一，输出的时候路中可能经过救护车数量为零的点。
最后看别人写的，66行加上等号就是对的，不加就是错的，还不知道为什么要加。
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int n1, n2, k, m, w[15], c, G[1020][1020], d[1020], mindis, maxamb, minP;
char str1[10], str2[10];
bool visit[1020];
vector<int> pre[15][1020], tempPath, path;
int getnum(char str[])
{int sum = 0;if(str[0] == 'A'){for(int i = 2; i < strlen(str); i++){sum = sum * 10 + str[i] - '0';}sum += n1;}else{for(int i = 0; i < strlen(str); i++){sum = sum * 10 + str[i] - '0';}}return sum;
}
void Dijkstra(int s)
{fill(visit, visit + 1020, false);fill(d, d + 1020, INF);d[s] = 0;for(int i = 1; i <= n1 + n2; i++){int u = -1, min = INF;for(int j = 1; j <= n1 + n2; j++){if(visit[j] == false && min > d[j]){u = j;min = d[j];}}if(u == -1) return;visit[u] = true;for(int j = 1; j <= n1 + n2; j++){if(G[u][j] != INF && visit[j] == false){if(d[j] > d[u] + G[u][j]){d[j] = d[u] + G[u][j];pre[s - n1][j].clear();pre[s - n1][j].push_back(u);}else if(d[j] == d[u] + G[u][j]) pre[s - n1][j].push_back(u);}}}
}
void DFS(int s, int v)
{if(v == s){tempPath.push_back(v);int dis = 0, amb = w[s - n1], p = tempPath.size() - 1;for(int i = tempPath.size() - 1; i > 0; i--){dis += G[tempPath[i]][tempPath[i - 1]];}if(dis < mindis){path = tempPath;mindis = dis;maxamb = amb;minP = p;}else if(dis == mindis && amb > maxamb){path = tempPath;maxamb = amb;minP = p;}else if(dis == mindis && amb == maxamb && p < minP){path = tempPath;minP = p;}tempPath.pop_back();return;}tempPath.push_back(v);for(int i = 0; i < pre[s - n1][v].size(); i++){DFS(s, pre[s - n1][v][i]);}tempPath.pop_back();
}
void showresult()
{for(int i = path.size() - 1; i >= 0; i--){if(path[i] > n1) printf("A-%d", path[i] - n1);else printf("%d", path[i]);if(i) printf(" ");else printf("\n");}printf("%d\n", mindis);
}
int main()
{fill(G[0], G[0] + 1020 * 1020, INF);scanf("%d%d", &n1, &n2);for(int i = 1; i <= n2; i++){scanf("%d", &w[i]);}scanf("%d", &m);for(int i = 0; i < m; i++){scanf("%s%s%d", str1, str2, &c);int t1 = getnum(str1), t2 = getnum(str2);G[t1][t2] = G[t2][t1] = c;}for(int i = n1 + 1; i <= n1 + n2; i++){Dijkstra(i);}scanf("%d", &k);while(k--){scanf("%d", &c);path.clear();mindis = INF, maxamb = 0, minP = INF;for(int i = 1; i <= n2; i++){if(w[i]) DFS(i + n1, c);}if(path.size()){w[path[path.size() - 1] - n1]--;showresult();}else printf("All Busy\n");}return 0;
}