OpenCup 11.11.12

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cassert>

using namespace std;

#define pb push_back
#define mp make_pair
#define sz(A) (int)(A).size()

typedef long long LL;
typedef long double LD;

const int N = 2005, M = int(2e4), INF = int(1e9);
const LD eps = 1e-10;

int a[M], b[M], l[M], dist[N][N], from[N], n, m, opt = INF;
LD p, p1, dp[N][N];
vector<int> ans;

int main()
{
    cin >> n >> m >> p >> p1;

    dp[0][0] = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++) {
            dp[i + 1][j + 1] += dp[i][j] * p1;
            dp[i + 1][j] += dp[i][j] * (1 - p1);
        }

    for (int i = 0; i < m; i += 2) {
        cin >> a[i] >> b[i] >> l[i];
        a[i + 1] = b[i];
        b[i + 1] = a[i];
        l[i + 1] = l[i];
    }
    m *= 2;

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dist[i][j] = INF;

    dist[1][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (b[j] == n)
                    cerr << j << endl;

            if (dist[ b[j] ][i + 1] > dist[ a[j] ][i] + l[j]) {
                dist[ b[j] ][i + 1] = dist[ a[j] ][i] + l[j];
                from[ b[j] ] = a[j];

            }
        }
        if (dist[n][i + 1] != INF) {
            LD rest = 1;
            int ind = 0;
            for (int t = i + 2; t >= 0; t--) {
                if (rest - dp[i + 2][t] > p - eps) {
                    rest -= dp[i + 2][t];
                }
                else {
                    ind = t;
                    break;
                }
            }
            if (opt > dist[n][i + 1] + ind) {
                opt = dist[n][i + 1] + ind;
                int cur = n;
                ans.clear();
                while (cur != 1) {
                    ans.pb(cur);
                    cur = from[cur];
                }
                ans.pb(1);
            }
        }
    }

    cout << sz(ans) << endl;
    for (int i = sz(ans) - 1; i >= 0; i--)
        cout << ans[i] << " ";
    cout << endl;

    return 0;
}