File size: 846 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include <bits/stdc++.h>
using namespace std;
int main() {
// For [5,7], try a solution with 3 nodes (fewer than optimal 5)
// by having multiple edges with same weight
// Actually can't reduce below 5 for [5,7]
// What about self-referencing tricks?
// Node 1: START (in-degree 0)
// Node 2: END (out-degree 0)
// Can we do it in 2 nodes? No - need at least 3 edges (for 3-bit numbers)
// For 5=101: START->1->0->1->END
// For 6=110: START->1->1->0->END
// For 7=111: START->1->1->1->END
// Minimum is 5 nodes for [5,7]
cout << 5 << endl;
cout << "1 2 1" << endl; // START -> A (weight 1)
cout << "2 3 0 4 1" << endl; // A -> B(0), C(1)
cout << "1 5 1" << endl; // B -> END(1)
cout << "2 5 0 5 1" << endl; // C -> END(0), END(1)
cout << "0" << endl; // END
}
|