Testing handset viewing

[leppyr64]

#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <map>
using namespace std;
struct mycomparison
{
	bool operator() (const pair<int, int>& lhs, const pair<int, int>& rhs) const
	{
		return (lhs.first>rhs.first);
	}
};
int N;
bool visited[100001];
vector<pair<int, int> > edges[100001];
map<string, int> cities;
priority_queue<pair<int, int>, vector<pair<int, int> >, mycomparison > Q;
int main()
{
	int T,M,R,a,b,i;
	int loc, dist, nextloc, nextdist;
	char city[20];
	pair<int, int> S;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &N);
		cities.clear();
		for(i = 1; i <= N; i++)
		{
			edges[i].clear();
			scanf("%s", city);
			cities[std::string(city)] = i;
			scanf("%d", &M);
			while(M--)
			{
				scanf("%d %d", &a, &b);
				edges[i].push_back(make_pair(a,b));
			}
		}
		scanf("%d", &R);
		while(R--)
		{
			for(i = 1; i <= N; i++)
				visited[i] = false;
			scanf("%s", city);
			a = cities[std::string(city)];
			scanf("%s", city);
			b = cities[std::string(city)];
			// Add the initial state for the starting point
			Q.push(make_pair(0,a));
			while(!Q.empty())
			{
				S = Q.top();
				Q.pop();
				loc = S.second;
				dist = S.first;
				// Check to see that we haven't already found a shorter path to this node
				if(visited[loc])
					continue;
    			// This is the shortest path to this node, ignore all other possibilities for this node
			visited[loc] = true;

			// If this distance is greater than T, then no other time can come in under T, we're done
			if(loc == b)
			{
				printf("%d\n", dist);
				while(!Q.empty())
					Q.pop();
				break;
			}
			
			// If we haven't reached the end, push all the endpoints from this location onto the queue
			// if they haven't already been visited
			for(i = 0; i < edges[loc].size(); i++)
			{
				nextloc = edges[loc][i].first;
				nextdist = edges[loc][i].second + dist;
				if(!visited[nextloc])
					Q.push(make_pair(nextdist,nextloc));
			}
		}
		if(!visited[b])
			printf("-1\n");
	}
}
return 0;
}

[leppyr64]

[bbone=cpp,73]

include

include

include

include

include

using namespace std;

struct mycomparison
{
bool operator() (const pair& lhs, const pair& rhs) const
{
return (lhs.first>rhs.first);
}
};

int N;
bool visited[100001];
vector > edges[100001];
map cities;
priority_queue, vector >, mycomparison > Q;

int main()
{
int T,M,R,a,b,i;
int loc, dist, nextloc, nextdist;
char city[20];
pair S;

scanf("%d", &T);
while(T--)
{
	scanf("%d", &N);

	cities.clear();
	for(i = 1; i <= N; i++)
	{
		edges[i].clear();
		scanf("%s", city);
		cities[std::string(city)] = i;
		scanf("%d", &M);
		while(M--)
		{
			scanf("%d %d", &a, &b);
			edges[i].push_back(make_pair(a,b));
		}
	}

	scanf("%d", &R);
	while(R--)
	{
		for(i = 1; i <= N; i++)
			visited[i] = false;
		scanf("%s", city);
		a = cities[std::string(city)];
		scanf("%s", city);
		b = cities[std::string(city)];

		// Add the initial state for the starting point
		Q.push(make_pair(0,a));
		while(!Q.empty())
		{
			S = Q.top();
			Q.pop();
			loc = S.second;
			dist = S.first;

			// Check to see that we haven't already found a shorter path to this node
			if(visited[loc])
				continue;

			// This is the shortest path to this node, ignore all other possibilities for this node
			visited[loc] = true;

			// If this distance is greater than T, then no other time can come in under T, we're done
			if(loc == b)
			{
				printf("%d\n", dist);
				while(!Q.empty())
					Q.pop();
				break;
			}
			
			// If we haven't reached the end, push all the endpoints from this location onto the queue
			// if they haven't already been visited
			for(i = 0; i < edges[loc].size(); i++)
			{
				nextloc = edges[loc][i].first;
				nextdist = edges[loc][i].second + dist;
				if(!visited[nextloc])
					Q.push(make_pair(nextdist,nextloc));
			}
		}
		if(!visited[b])
			printf("-1\n");
	}
}
return 0;

}

[/bbone]

[leppyr64]

Boo! The code doesn't work properly on an iPhone or the HTC Desire. Have to test the torch now.

[leppyr64]

As I found out, they do work on the iPhone. You scroll down with two fingers. CodeToGo is well worth the investment if you do use an iPhone.