up vote 3 down vote favorite

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 <list>
#include <vector>
#include <string>
#include <queue>
#define MALLOC(name,type,n) (name=(type*)malloc(sizeof(type)*(n)))
using namespace std;
typedef unsigned long long int ll;
#include <cstdio>
#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(;(c<48 || c>57);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<int ,int> ii;
typedef std::vector<int> vi;
typedef std::vector<ii> vii;
std::vector<vii> graph;
typedef pair<string,int> si;
vector<vector<si> > h_table;
vi sourced;
vector< vector<ll> > dijkstra_data;

Gets vertex position from name:

int get_index(const string &s)
{
    int h=hash(s);
    for (int i = 0; i < h_table[h].size(); ++i){
        if(h_table[h][i].first==s)
        {
            return h_table[h][i].second;
        }
    }
}

void dijkstra(int,int);



int main()
{
    //freopen("input","r",stdin);
    int tc;
    cin>>tc;
    while(tc--)
    {
        scanint(V);
        h_table.clear();
        h_table.assign(1000,vector<si>());
        graph.clear();
        graph.assign(V+1,vii());
        sourced.clear();
        sourced.assign(V+1,0);
        dijkstra_data.clear();
        dijkstra_data.assign(V+1,std::vector<ll> ());

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


        for (int i = 1; i < V+1; ++i){
            scanstring(name);
            si x(name,i);
            h_table[hash(name)].push_back(x);
            scanint(e);
            while(e--)
            {
                scanint(v);scanint(c);
                graph[i].push_back(ii(v,c));
            }
        }
        int cases;
        scanint(cases);
        string src,dest;
        while(cases--)
        {
            scanstring(src);
            scanstring(dest);
            int isrc=get_index(src),idest=get_index(dest);
            if(sourced[isrc])
                printf("%llu\n", dijkstra_data[isrc][idest]);
            else
                dijkstra(isrc,idest);

        }

    }

    return 0;
}


void dijkstra(int src,int dest)
{
    vi visited(V+1,0);
std::vector<ll> dist(V+1,INF);
    dist[src]=0;
    typedef pair<int,ll> il;
    typedef std::vector<il> vil;
    std::priority_queue<il,vil,greater<il> > pq;
    pq.push(il(src,0));
    int n=1;
    while(n<V&&!pq.empty())
    {
        il x=pq.top();
        pq.pop();
        int sv=x.first; ll sd=x.second;
        if(visited[sv])
            continue;
        visited[sv]=1;n++;dist[sv]=sd;
        for (int i = 0; i < graph[sv].size(); ++i){
            ll d1=sd+graph[sv][i].second;
            ll d2=dist[graph[sv][i].first];
            if(d1<d2)
            {
                dist[graph[sv][i].first]=d1;
                pq.push(il(graph[sv][i].first,d1));
            }
        }
    }
    dijkstra_data[src].assign(dist.begin(),dist.end());
    sourced[src]=1;
    printf("%llu\n", dist[dest]);
}

and TLE is my result.

I know I could use my own heap instead of STL std::priority_queue. I'm new to the STL so I want to know if there is anything associated with STL where I have caused more overhead.

share|improve this question
2  
Note: for(;(c<48 || c>57);c = gc()); is an endless loop should c equal EOF. – chux Dec 15 '13 at 16:35
1  
All those STL #includes should use <>, not "". You also use <stdio.h>, printf, and malloc, which indicate C code instead of C++ code. – Jamal♦ Dec 15 '13 at 16:38
    
Note: int hash(const string &x) returns values -999 to 999. I suspect this is a problem for h_table[h]. – chux Dec 15 '13 at 16:40
1  
Yes, it won't cause immediate problems, but "string.h" would only be needed if that happens to be your own defined header in the same directory. If you're just using std::string, then only <string> is needed. More information here. Unless you have a necessary reason for these extra headers, your code will just look less like C++. – Jamal♦ Dec 15 '13 at 20:14
1  
@user2058841 if gc() returns EOF, in for(;(c<48 || c>57);c = gc());, the for loop does not exit. Instead the loop repeats. c on the next call will get set to EOF again and again. – chux Dec 15 '13 at 21:45
up vote 3 down vote

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.

share|improve this answer
up vote 2 down vote

In your hash function, you're doing x.size() in a loop, which will slow the function down quite a lot for a long string. Instead, store the size in a variable and compare to that

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

Also, you're using namespace::std. Don't do that, for good reasons. As well as this, if you're having to explain your variable names that last for a while and actually require explanation (I'm looking at V, u, v, c), maybe name them something else? Or at least include comments if they're the convention that people would expect that would give someone who doesn't know the convention a chance.

share|improve this answer
    
Calling std::string::size() is constant time, see here: std::basic_string::size(). To be constant size it's either implemented as an internal size member in the string or as a pointer arithmetic with start and end pointers. Both should be inlined by the compiler. This has a negligible effect on the run-time. – Emily L. Oct 30 '14 at 15:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.