G 小红的数轴移动(二)

G 小红的数轴移动(二）

因为比较擅长图论,所以在做题时尝试用图论的思想去解决这道题。

首先分析题意，小红在原点时会停止移动,即她在移动到原点后的移动序列都不提供贡献,所以题意转化为了求小红初始位置在 $x$ ,移动到原点所需价值最小的序列，这是不是很像求最短路，最终答案即为从x点到原点的最短路，观察题目数据范围。

发现 $-100 \leq x \leq 100，a_i \leq 100$ ，所以小红在数轴上所能到达的点也在 $-100$ 到 $100$ 之间。接下来我们考虑如何建边。对于负值不太好处理，我们可以对于每个值都加上一个偏移量使其成为正数，我们取偏移量为 $100$ ，对于每个 $a_i$ 我们依次遍历 $j$ 从 $0$ 到 $200$ ，当 $j>100$ 时，我们建边从 $j$ 到 $j-a_i$ ，边权为 $a_i$ ，代表从 $x$ 的正半轴向原点方向走，当 $j<100$ 时，我们建边从 $j$ 到 $j a_i$ ，边权为 $a_i$ ，代表从 $x$ 的负半轴向原点方向走，然后跑最短路，但是这时候会发现一个问题，例如对于样例

2 1
5 3

我们手模很容易发现他是无解的，但是建边完后跑最短路是有解的， $101$ -> $98$ -> $103$ -> $100$ ，我们发现 $3$ 走了两回，那么怎么避免这个问题呢，我们用一个标记数组标记这条路径上走了哪条边，在跑最短路的时候将这个标记数组传下去。

最后将 $x$ + $100$ 作为起点跑一下最短路就可以，最终答案即为 $dis[100]$ ，要求输出选择方案，我们可以开一个 $pre$ 数组记录每个点最短路的前驱，最后把路径还原出来，对于不在最短路上的操作，我们先输出完最短路径后按序输出即可。对于无解的情况，即到不了原点，最终移动的总距离即为 $n$ 次操作移动的距离和，序列从 $1-n$ 输出即可

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e2 + 5;
int __ = 1, n = 0, m, x;
string s;
int a[N];
struct info
{
    int v, w, id;
    vector<bool> vv;
    bool operator<(const info &a) const
    {
        return w > a.w;
    }
};
struct ifo
{
    int v, w, id;
};
vector<ifo> e[N];
int dis[N], pre[N], preid[N];
bool vis[N];
void dij(int root)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[root] = 0;
    priority_queue<info> q;
    vector<bool> vv(n + 1, 0);
    q.push({root, 0, 0, vv});
    while (!q.empty())
    {
        int x = q.top().v;
        auto vs = q.top().vv;
        q.pop();
        if (vis[x])
            continue;
        vis[x] = 1;
        for (auto [v, w, id] : e[x])
        {
            if (dis[v] > dis[x] + w && !vs[id])
            {
                dis[v] = dis[x] + w;
                pre[v] = x;
                preid[v] = id;
                vector<bool> vvs = vs;
                vvs[id] = 1;
                q.push({v, dis[v], id, vvs});
            }
        }
    }
    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)
                e[j].push_back({j - a[i], a[i], i});
            else if (j < 100)
                e[j].push_back({j + a[i], a[i], i});
        }
    }
    dij(x + 100);
    if (dis[100] == 0x3f3f3f3f3f3f3f3f)
    {
        cout << sum << endl;
        for (int i = 1; i <= n; i++)
        {
            cout << i << ' ';
        }
    }
    else
    {
        cout << dis[100] << endl;
        int nxt = 100;
        vector<int> ans;
        vector<bool> vis(n + 1, 0);
        if (pre[nxt])
        {
            while (true)
            {
                ans.push_back(preid[nxt]);
                vis[preid[nxt]] = 1;
                if (pre[nxt] == x + 100)
                    break;
                nxt = pre[nxt];
            }
        }
        reverse(ans.begin(), ans.end());
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i])
            {
                ans.push_back(i);
            }
        }
        for (auto i : ans)
        {
            cout << i << ' ';
        }
    }
    return;
}
int32_t main()
{
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    // cin >> __;
    while (__--)
        solve();
    return 0;
}