How big is your graph? Do you want to solve the problem for a city, a coutry or even a continent?
Each is about a magnitude larger than the other and may mean you need different approaches. Here are sizes for a few input sets:

|_. input |_. Europe |_. USA/CAN |_. USA (Tiger) |
| #nodes | 18 029 721 | 18 741 705 | 24 278 285 |
| #directed edges | 42 199 587 | 47 244 849 | 58 213 192 |
| #road categories | 13 | 13 | 4 |

From the given time limit it's obvious that pure Dijkstra won't do and we need to look at how other algorithms behave like A star search or an algorithm based on 'Highway hierarchies':http://algo2.iti.kit.edu/schultes/hwy/esa06HwyHierarchies.pdf

From the given time limit it's obvious that pure Dijkstra won't do and we need to look at how other algorithms behave like A star search or http://algo2.iti.kit.edu/schultes/hwy/esa06HwyHierarchies.pdf