STL and Dijkstra's algorithm optimization

This is the problem and my solution to this is:

#include "iostream"
#include "stdio.h"
#include "algorithm"
#include "math.h"
#include "string.h"
#include "time.h"
#include "stdlib.h"
#include 
#include 
#include 
#include 
#define MALLOC(name,type,n) (name=(type*)malloc(sizeof(type)*(n)))
using namespace std;
typedef unsigned long long int ll;
#include 
#define gc getchar_unlocked
const ll INF=~0;

Fast input and output:

void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int m=0;
    if(c=='-')
        m=1;
    for(;(c57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(m==1)
        x*=-1;
}
void scanstring(string& str)
{
    str.clear();
    str.reserve(20);
    char x;
    while((x=getchar_unlocked())!=EOF&&x!='\n'&&x!=' ')
        str.push_back(x);
}

I'm hashing the names for that specific vertex.

The simple hash function:

int hash(const string &x)
{
    int y=0;
    for (int i = 0; i < x.size(); ++i){
        y+=x[i]*137;
    }
    return y%1000;
}

V - total number of vertices

u, v, c -source, destination, cost

int V,u,v,c,e;  
string name;
typedef pair ii;
typedef std::vector vi;
typedef std::vector vii;
std::vector graph;
typedef pair si;
vector > h_table;
vi sourced;
vector > dijkstra_data;

Gets vertex position from name:

```
int get_index(const string &s)
{
int h=hash(s);
for (int i = 0; i >tc;
while(tc--)
{
scanint(V);
h_table.clear();
h_table.assign(1000,vector());
graph.clear();
graph.assign(V+1,vii());
sourced.clear();
sourced.assign(V+1,0);
dijkstra_data.clear();
dijkstra_data.assign(V+1,std::vector ());

// dijkstra_data stores all shortest paths from a source that have been calculated till now

for (int i = 1; i dist(V+1,INF);
dist[src]=0;
typedef pair il;
typedef std::vector vil;
std::priority_queue > pq;
pq.push(il(src,0));

You're putting too much effort into your input reading. Just use cin it'll be fast enough. The problem is in your algorithm, not the input parsing. The note about input size on the site is meant for languages where naive handling of input can be slow, e.g. Java. C++ is not affected by this.

Instead of implementing your own hash function you can use std::hash (since C++11). Or simply use std::unordered_map which is basically a hash map, and save yourself a lot of trouble.

Your naming of types and variables is absolutely horrific. Use descriptive names, a type called ii is not descriptive.

Macros are evil don't use them like that.

Now to the core of your problem. You're applying Dijkstra's algorithm for each of the queries in the test case. This is where your slow down is.

You need to use the Floyd-Warshall Algorithm. This will bring down your run-time and make you get past the TLE with flying colours.

StackExchange Code Review Q#37422, answer score: 4