给出你说的这两种方法的c++代码

方法一：贪心算法的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1000;
const int INF = 0x3f3f3f3f;

int n, m, d, Pmin, Pmax;
int dis[MAXN][MAXN], d[MAXN];
bool used[MAXN];

struct node {
    int id, dis;
    bool operator<(const node& a) const {
        return dis > a.dis; // 从大到小排序
    }
};

vector<int> ans;

void dijkstra(int s) {
    fill(d, d + n, INF);
    fill(used, used + n, false);
    d[s] = 0;

    while (true) {
        int v = -1;
        for (int u = 0; u < n; ++u) {
            if (!used[u] && (v == -1 || d[u] < d[v]))
                v = u;
        }
        if (v == -1) break;
        used[v] = true;
        for (int u = 0; u < n; ++u) {
            if (dis[v][u] != -1) {
                int tmp = d[v] + dis[v][u];
                if (tmp < d[u])
                    d[u] = tmp;
            }
        }
    }
}

int main() {
    cin >> n >> m >> d >> Pmin >> Pmax;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dis[i][j] = -1;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = w;
    }

    dijkstra(0);

    vector<node> vec;
    for (int i = 1; i < n; ++i)
        vec.push_back({ i, d[i] });

    sort(vec.begin(), vec.end());

    int cur = Pmax;
    for (int i = 0; i < vec.size(); ++i) {
        int id = vec[i].id;
        int dis = vec[i].dis;
        if (dis <= d)
            break;
        if (cur - (dis - d) * Pmin <= 0) {
            ans.push_back(id);
            cur = Pmax;
        }
        cur -= (dis - d) * Pmin;
    }

    if (cur < Pmin * d) {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }

    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); ++i)
        cout << ans[i] << endl;

    return 0;
}

方法二：动态规划算法的C++实现：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1000;
const int INF = 0x3f3f3f3f;

int n, m, d, Pmin, Pmax;
int dis[MAXN][MAXN], d[MAXN], f[MAXN], pre[MAXN];

int dp(int x) {
    if (x == 0) return 0;
    if (f[x] != -1) return f[x];

    f[x] = INF;
    for (int i = 0; i < x; ++i) {
        if (dis[i][x] >= 0 && dis[i][x] <= d && d - dis[i][x] >= Pmin * (x - i)) {
            int tmp = dp(i);
            if (tmp < f[x]) {
                f[x] = tmp;
                pre[x] = i;
            }
        }
    }
    ++f[x];
    return f[x];
}

int main() {
    cin >> n >> m >> d >> Pmin >> Pmax;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dis[i][j] = -1;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = w;
    }

    memset(f, -1, sizeof(f));
    int ans = dp(n - 1);

    if (ans == INF) {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }

    cout << ans << endl;

    vector<int> res;
    int cur = n - 1;
    while (cur != 0) {
        res.push_back(cur);
        cur = pre[cur];
    }
    res.push_back(0);

    for (int i = res.size() - 1; i >= 0; --i)
        cout << res[i] << endl;

    return 0;
}