Travelling Problem with Constraints Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance.

You start your travel at a given node, say $1$, and end your travel at a given node, say $12$. Your travel has $T$ time steps. At time step $t=1$ you must visit one of nodes $\{1,7,4\}$, at time step $t=2$ you must visit one of the nodes $\{7,3,45,9\}$, and so on. In other words, at a given time step, you are given a set with at minimum $1$ and at maximum $K\leq N$ nodes. Choose the nodes for all time steps such that the cumulative distance is minimized.

Am I correct, that such problem is NP hard? Given $T$ time steps and that at most $K$ nodes are possible at each time step, the complexity would be $O(K^T)$, right?

What algorithms could be applicable or useful for such a problem? In my scenario, $T$ can be very large (up to 20,000) but $K$ is rather low (10 on average, at most 100).

(Edit) - I encountered the problem in a diary of a traveller. For example, you know that a traveller started his journey at some location. For every journey entry, besides the raw text, the writer in the title writes a date  and a location name. 

The problem is there often exist several different coordinates for a location name (i.e., multiple locations exists with the same name). An (I think reasonable) assumption I have come to, is that the shortest possible path (from start to finish) should approximate the travelled route quite well. I have a data set of multiple travellers with diaries like this and want to plot the routes onto a map (and hope to display a travelled route approximately in the way which in it was really travelled). 

I have not yet come up with any good and general solution (besides brute-force computing the distance of every possible route, which may be impossible because there exist tons of diary entries and so many location names have multiple possible coordinates).
The problem can be solved efficiently: in $O(K^2 T \log (KT))$ time.

Build a graph where each vertex corresponds to a pair $(t,i)$, where $t$ is a time step and $i$ is one of the nodes that is allowed to be visited at time $t$.  Add edges from $(t,i)$ to $(t+1,j)$ for every $t,i,j$, with a length that corresponds to the travel time from $i$ to $j$.  Add a source node $s$ with edges from $s$ to each $(1,i)$ of length 0, and a sink node $t$ with edges from each $(T,i)$ to $t$ of length 0.  Then, find the shortest path in this graph from $s$ to $T$.

The graph has $O(KT)$ vertices and $O(K^2T)$ edges, so Dijkstra's algorithm for finding shortest paths will run in $O(K^2 T \log (KT))$ time.