Problem: ethan_path (2018 round2)

Ethan is doing his third programming assignment: finding the shortest path
between two nodes in a graph.

Given an undirected, weighted graph with **N** nodes (numbered from 1 to
**N**), having no self-loops or duplicate edges, Ethan must compute the length
of the shortest path from node 1 to node **N**. Ethan has implemented an
algorithm to solve this problem, described by the following pseudocode:

  1. Set _i_ to be equal to 1, and _d_ to be equal to 0
  2. If _i_ is equal to **N**, output _d_ and stop
  3. Find the edge incident to node _i_ that has the smallest weight (if no edges are incident to _i_ or if there are multiple such edges tied with the smallest weight, then crash instead)
  4. Increase _d_ by the weight of this edge, and set _i_ to be equal to the other node incident to this edge
  5. Return to Step 2

Since you were nice to Ethan on his second assignment, and since that
encouragement clearly hasn't helped improve the quality of his code, you'd
like to find a graph that shows as clearly as possible why this solution is
incorrect.

You're given the number of nodes in the graph **N**, as well as the maximum
allowable edge weight **K** (each edge's weight must be an integer in the
interval [1, **K**]). Under these constraints you want to maximize the
absolute difference between Ethan's output and the actual shortest distance
between nodes 1 and **N**. However, you don't want Ethan's algorithm to either
crash or run forever. Note that node **N** must actually be reachable from
node 1 in the graph, though the graph may be otherwise disconnected. You can
output any valid graph which gets the job done.

### Input

Input begins with an integer **T**, the number of graphs. For each graph,
there is a line containing the space-separated integers **N** and **K**.

### Output

For the _i_th graph, first output a line containing "Case #_i_: " followed by
the maximum possible absolute difference between Ethan's algorithm's output
and the correct answer. Then, output a line containing as single integer
**E**, the number of edges in your chosen graph which yields the above maximum
absolute difference. Then, output **E** lines, the _j_th of which contains
three integers **Uj**, **Vj**, and **Wj** denoting that there is an edge
between nodes **Uj** and **Vj** with weight **Wj**.

Note that there must be no self-loops (no edge may connect a node to itself),
and no two edges may connect the same unordered pair of nodes.

### Constraints

1 ≤ **T** ≤ 200  
2 ≤ **N** ≤ 50  
1 ≤ **K** ≤ 50  

### Explanation of Sample

In the first case, there are exactly two possible valid graphs, either of
which would be accepted:

      1
      1 2 1
      1
      2 1 1

In each of the above graphs, Ethan's algorithm's answer and the correct answer
are both equal to 1. There's an absolute difference of 0 between those
answers, which is the maximum possible absolute difference.

In the second case, one possible graph which would be accepted is as follows
(with Ethan's algorithm's answer and the correct answer both equal to 42):

      1
      1 2 42

In the third case, one possible graph which would be accepted is as follows
(with Ethan's algorithm's answer and the correct answer both equal to 1):

      3
      1 2 2
      4 1 1
      4 2 1

Putting those together, the following is one possible sequence of outputs for
the first 3 cases which would be accepted:

      Case #1: 0
      1
      1 2 1
      Case #2: 0
      1
      1 2 42
      Case #3: 0
      3
      1 2 2
      4 1 1
      4 2 1

Do not output the line "**Multiple possible accepted graphs**".



Sample input:
6
2 1
2 50
4 2
5 5
42 48
47 38


Sample output:
Case #1: 0
Multiple possible accepted graphs
Case #2: 0
Multiple possible accepted graphs
Case #3: 0
Multiple possible accepted graphs
Case #4: 5
Multiple possible accepted graphs
Case #5: 1059
Multiple possible accepted graphs
Case #6: 665
Multiple possible accepted graphs



Code: // Ethan Finds the Shortest Path
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

struct Edge {
	int a,b,w;
	Edge(int a,int b,int w):a(a),b(b),w(w){}
};

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N,K;
	int i,d;
	vector<Edge> E;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(K);
			// construct graph
			E.clear();
			d=K;
			E.pb(Edge(1,N,K--));
				if ((N<3) || (K<2))
					d=0;
				else
				{
					FoxI(i,2,N-1)
					{
						d-=K;
						E.pb(Edge(i-1,i,K--));
							if ((K==1) || (i==N-1))
							{
								d-=K;
								E.pb(Edge(i,N,K));
								break;
							}
					}
				}
			// output
			printf("Case #%d: %d\n%d\n",t,Abs(d),Sz(E));
				Fox(i,Sz(E))
					printf("%d %d %d\n",E[i].a,E[i].b,E[i].w);
		}
	return(0);
}