原题链接
https://ac.nowcoder.com/acm/contest/91177/G
题面
小红站在数轴的x点上，她准备进行n次操作，每次操作如下：
1、若小红站在原点，则原地不动。
2、否则按朝原点的方向，移动a[i]距离。
小红可以自己选择操作的先后次序。她希望给出一个方案，使得最终移动的总距离最小，你能帮帮她吗？
解题思路
可以尝试使用图论最短路的方式，先考虑怎么建图，自然是把数轴上的整数点作为图的顶点，根据题面给出的数据范围，我们可以得知，数的范围只有[-100, 100]，负数不是很方便作为图的顶点来建图，所以我们做一下偏移，将数轴范围向右偏移100，也就是[0, 200]。
很显然a[i]是作为边权的，我们每输入一个a[i]，都将a[i]按照题目规矩边权给[0, 200]建边。
图建好之后就可以开始跑Dijsktra算法求从x到0的最短路了，但是这一题当中我们要注意的问题是，题目给出的规矩是每个a[i]只可以使用一次，所以在用a[i]建边的时候我们需要给边一个标识，用a[i]建的边标识为i，所以我们在使用Dijkstra求最短路的过程中，我们要记录每个最短路方案中所用到的边的标识，以防在同一个最短路方案中使用多次（并且最终输出方案的时候也用得上）。
综上所述，邻接表结构体的结构为：
struct edge {int v, w, edgeId; // 到达点、边权、边标识
};
建边的代码为：
for (int i = 1; i <= n; i++) {cin >> a[i];for (int j = 0; j <= 200; j++) {// 按照题目所给的规矩来建边，按朝原点的方向，移动a[i]距离。if (j > 100)G[j].push_back({j - a[i], a[i], i});if (j < 100)G[j].push_back({j + a[i], a[i], i});}
}
详细的细节不赘述，见完整代码和注释。
代码（CPP）
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl "\n"
const int maxn = 2e2 + 10;
const int INF = 0x3fffffff;
struct edge { // 邻接表的边结构int v, w, edgeId; // 到达点、边权、边标识
};
struct info { // 用于优先队列维护int v, w, edgeId;set<int> edgeSet;bool operator < (const info &other) const {return w > other.w;}
};
vector<edge> G[maxn];
int pre[maxn], preEdge[maxn];
int dis[maxn];
bool vis[maxn];
int n, x, a[maxn];void dijkstra(int start) {fill(dis, dis + 205, INF);priority_queue<info> pq;dis[start] = 0;pq.push({start, 0, 0});pre[start] = start;while (!pq.empty()) {int u = pq.top().v;int w = pq.top().w;int edgeId = pq.top().edgeId;auto edgeSet = pq.top().edgeSet;pq.pop();if (vis[u])continue;vis[u] = true;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i].v;int w = G[u][i].w;int nEdgeId = G[u][i].edgeId;if (dis[u] + w < dis[v] && !edgeSet.count(nEdgeId)) {dis[v] = dis[u] + w;auto newEdgeSet = edgeSet;newEdgeSet.insert(nEdgeId);pre[v] = u;preEdge[v] = nEdgeId;pq.push({v, dis[v], nEdgeId, newEdgeSet});}}}
}vector<int> edges;
void getPath(int u) {if (u == pre[u]) {return;}getPath(pre[u]);edges.push_back(preEdge[u]);return;
}void solve() {cin >> n >> x;int sum = 0;for (int i = 1; i <= n; i++) {cin >> a[i];sum += a[i];for (int j = 0; j <= 200; j++) { // 建边if (j > 100)G[j].push_back({j - a[i], a[i], i});if (j < 100)G[j].push_back({j + a[i], a[i], i});}}dijkstra(x + 100);if (dis[100] == INF) {cout << sum << endl;for (int i = 1; i <= n; i++) {if (i != 1)cout << " ";cout << i;}return;}getPath(100);cout << dis[100] << endl;vector<int> has(n + 5);for (int i = 0; i < edges.size(); i++) {has[edges[i]] = true;cout << edges[i] << " ";}for (int i = 1; i <= n; i++) {if (!has[i]) {cout << i << " ";}}
}int main() {
// freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);solve();return 0;
}
