Proving following problem NP Hard using known NP Hard partition problem
Assuming that an "airport" cannot be visited more than once, you can reduce HAMILTONIAN PATH to your problem: given a graph $G = (V,E)$, $|V|=n$; suppose that there are two airlines such that $E(1)=E(2)=E$ (i.e. both airlines cover all edges). Then set the price of each edge = $1$. One of the two companies gives no discount, the other gives a (big) discount $d$% (such that $n - \frac{n * d}{100} &lt; 1$) if the cost of the travel is $\geq n$.

Then $G$ has an Hamiltonian path from $s$ to $t$ if and only if the minimum cost of the travel is $&lt; 1$ (i.e. the airline which gives the discount is more convenient).

Note: if an airport can be visited more than once I think that the problem is no more NP-hard (but  I didn't think of it too much). In this case a modified version of a shortest path algorithm should work: just augment the shortest path traversing multiple times an edge of each airline and check if the total cost decreases after reaching the discount treshold.