p236.ans1
======================
4
3 4 1 2

=================
p236.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

struct Edge {
    int u, v, c, t;
};

int n, m;
vector<Edge> edges;
vector<double> dist;
vector<int> par;

void read() {
    cin >> n >> m;
    edges.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].c >> edges[i].t;
    }
}

pair<bool, vector<int>> check(double x) {
    dist.assign(n + 2, 1e18);
    par.assign(n + 2, -1);

    int source = n + 1;
    dist[source] = 0;

    for(int i = 0; i < n; i++) {
        for(auto& e: edges) {
            double weight = e.t * x - e.c;
            if(dist[e.u] < 1e17 && dist[e.u] + weight < dist[e.v]) {
                dist[e.v] = dist[e.u] + weight;
                par[e.v] = e.u;
            }
        }

        for(int v = 1; v <= n; v++) {
            if(dist[source] < dist[v]) {
                dist[v] = dist[source];
                par[v] = source;
            }
        }
    }

    int cycle_node = -1;
    for(auto& e: edges) {
        double weight = e.t * x - e.c;
        if(dist[e.u] < 1e17 && dist[e.u] + weight < dist[e.v]) {
            cycle_node = e.v;
            break;
        }
    }

    if(cycle_node == -1) {
        return {false, {}};
    }

    for(int i = 0; i < n; i++) {
        cycle_node = par[cycle_node];
    }

    vector<int> cycle;
    int curr = cycle_node;
    do {
        cycle.push_back(curr);
        curr = par[curr];
    } while(curr != cycle_node);

    reverse(cycle.begin(), cycle.end());
    return {true, cycle};
}

void solve() {
    // We maximize the cycle ratio (sum of costs) / (sum of times). Binary search
    // the answer x: a cycle with ratio > x exists iff some cycle has positive
    // sum of (c - t*x), equivalently a negative cycle under edge weight
    // t*x - c. We detect such a cycle with N relaxation rounds of Bellman-Ford
    // from a virtual super-source connected to every node, then one extra round
    // to find an edge that still relaxes; walking N parent steps lands inside the
    // negative cycle, which we trace via the parent array and report.

    double l = 0.0, r = 200.0;
    for(int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;
        auto [has_cycle, cycle] = check(mid);
        if(has_cycle) {
            l = mid;
        } else {
            r = mid;
        }
    }

    auto [has_cycle, cycle] = check(l);
    if(!has_cycle) {
        cout << "0\n";
        return;
    }

    cout << cycle.size() << "\n";
    cout << cycle << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p236.in1
======================
4 5
1 2 5 1
2 3 3 5
3 4 1 1
4 1 5 2
2 4 1 10

=================
statement.txt
======================
236. Greedy Path
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



There are N towns and M routes between them. Recently, some new travel agency was founded for servicing tourists in these cities. We know cost which tourist has to pay, when traveling from town i to town j which equals to Cij and time needed for this travel - Tij. There are many tourists who want to use this agency because of very low rates for travels, but agency still has only one bus. Head of agency decided to organize one big travel route to gain maximal possible amount of money. Scientists of the company offer to find such a cyclic path G, when greedy function f(G) will be maximum. Greedy function for some path is calculated as total cost of the path (sum of Cij for all (i,j) - routes used in path) divided by total time of path (similar to Cij). But nobody can find this path, and Head of the company asks you to help him in solving this problem.

Input
There are two integers N and M on the first line of input file (3<=N<=50). Next M lines contain routes information, one route per line. Every route description has format A, B, Cab, Tab, where A is starting town for route, B - ending town for route, Cab - cost of route and Tab - time of route (1<=Cab<=100; 1<=Tab<=100; A<>B). Note that order of towns in route is significant - route (i,j) is not equal to route (j,i). There is at most one route (in one direction) between any two towns.

Output
You must output requested path G in the following format. On the first line of output file you must output K - number of towns in the path (2<=K<=50), on the second line - numbers of these towns in order of passing them. If there are many such ways - output any one of them, if there are no such ways - output "0" (without quotes).

Sample test(s)

Input
4 5
1 2 5 1
2 3 3 5
3 4 1 1
4 1 5 2
2 4 1 10

Output
4
1 2 3 4
Author: Sergey Simonchik
Resource:   ---
Date:   December, 2003


=================
