创新的产品设计_网站软件下载安装免费版_app推广平台接单渠道_搜索引擎优化方法有哪些

 

 

 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 510;
const int INF = 1000000000;
int c, tgt, n, m, G[maxn][maxn], bikeNum[maxn];
int dis[maxn],vis[maxn]={0},minNeed = INF, minRemain = INF;
vector<int> path,tempPath;
vector<int> pre[maxn];int findNotFoundMin(){int minIdx=-1,minDis=INF;for(int i = 0; i <= n; i++){if(vis[i] == 0 && dis[i] < minDis){minDis = dis[i];minIdx = i;}}return minIdx;
}void Dijkstra(){fill(dis, dis+maxn, INF);dis[0] = 0;for(int i = 0; i <= n; i++){int min = findNotFoundMin();if(min == -1) break;vis[min] = 1;for(int j = 0; j <= n; j++){if(vis[j] == 0 && G[min][j] != INF){if(G[min][j]+dis[min] < dis[j]){dis[j] = G[min][j]+dis[min];pre[j].clear();pre[j].push_back(min);}else if(G[min][j]+dis[min] == dis[j]){pre[j].push_back(min);}}}}
}
void DFS(int v){if(v == 0){tempPath.push_back(v);int need=0,remain=0;for(int i = tempPath.size()-1; i >= 0; i--){int idx = tempPath[i];if(bikeNum[idx] > 0){remain += bikeNum[idx];}else{if(remain > abs(bikeNum[idx])){remain -= abs(bikeNum[idx]);}else{need += abs(bikeNum[idx]) - remain;remain = 0;}}}if(need < minNeed){minNeed = need;minRemain = remain;path = tempPath;}else if(need == minNeed && remain < minRemain){minRemain = remain;path = tempPath;}tempPath.pop_back();return;}tempPath.push_back(v);for(int i = 0; i < pre[v].size(); i++){DFS(pre[v][i]);}tempPath.pop_back();
}
int main() {scanf("%d%d%d%d", &c, &n, &tgt, &m);int si,sj,t;int tmp;for(int i = 1; i <= n; i++){scanf("%d", &tmp);bikeNum[i] = tmp - c / 2;}fill(G[0], G[0]+maxn*maxn, INF);for(int i = 0; i < m; i++){scanf("%d%d%d", &si, &sj, &t);G[si][sj] = t;G[sj][si] = t;}Dijkstra();DFS(tgt);printf("%d ", minNeed);for(int i = path.size()-1; i >= 0; i--){printf("%d", path[i]);if(i > 0){printf("->");}}printf(" %d\n", minRemain);return 0;
}