temporary
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 999999999;
int cmax, n, sp, m;
int minNeed = inf, minBack = inf;
int e[510][510], dis[510], weight[510];
bool visit[510];
vector<int> pre[510], path, temppath;
void dfs(int v) {
temppath.push_back(v);
if (v == 0) {
int need = 0, back = 0;
for (int i = temppath.size()-1; i >=0; i--) {
if (weight[i] > 0) {
back += weight[i];
}
else {
if (back > (0 - weight[i])) {
back += weight[i];
}
else {
need += (0 - weight[i]) - back;
back = 0;
}
}
}
if (back < minBack) {
minBack = back;
minNeed = need;
path = temppath;
}
else if(back==minBack&&need<minNeed){
minNeed = need;
path = temppath;
}
return;
}
for (int i = 0; i < pre[v].size(); i++) {
dfs(pre[v][i]);
}
temppath.pop_back();
}
int main() {
fill(dis, dis + 510, inf);
fill(e, e + 510*510, inf);
cin >> cmax >> n >> sp >> m;
for (int i = 1; i <= n; i++) {
cin >> weight[i];
weight[i] =weight[i]-cmax / 2;
}
for (int i = 0; i < m; i++) {
int a,b,temp;
cin >> a >> b >> temp;
e[a][b] = e[b][a] = temp;
}
dis[0] = 0;
for (int i = 0; i <= n; i++) {
int u = -1, min = inf;
for (int j = 0; j <= n; j++) {
if (visit[j] == false && dis[j] < min) {
min = dis[j];
u = j;
}
}
visit[u] = true;
for (int v = 0; v <= n; v++) {
if (visit[v] == false) {
if (dis[v] > dis[u] + e[u][v]) {
dis[v] = dis[u] + e[u][v];
pre[v].clear();
pre[v].push_back(u);
}
else if (dis[v] == dis[u] + e[u][v]) {
pre[v].push_back(u);
}
}
}
}
dfs(sp);
return 0;
}
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
更多精彩
