gistfile1.cpp

*/
#include <fstream>
using namespace std;
#define maxint 500000
class node
{
public:
	node(){next = NULL;}
	int weight;
	int name;
	node* next;
};
node* adjlist[52];
int dist[52];
int visit[52];

int nametodigit(char c)
{
	int ret;
	if (c<97)
		ret = c - 'A';
	else ret = c -'a'+26;
	return ret;
}

void addadj(int index,int end,int wt)
{
	if (!adjlist[index])
	{
		adjlist[index] = new node;
		adjlist[index]->name = end;
		adjlist[index]->weight = wt;
	}
	else
	{
		node* p = adjlist[index];
		node* q = NULL;
		while (p)
		{
			q = p;
			p = p->next;
		}
		q->next = new node;
		q->next->name = end;
		q->next->weight = wt;//easy to forget next!!

	}
}
int main()
{
	ifstream fin("comehome.in");
	ofstream fout("comehome.out");
	int p;
	fin>>p;
	char end,start;
	int wt;
	for (int i =0;i<p ;i++)
	{
		fin>>end>>start>>wt;
	
			addadj(nametodigit(start),nametodigit(end),wt);
			addadj(nametodigit(end),nametodigit(start),wt);//add the edge twice
		
	}

	//dijkstra
	for (int i=0 ; i<52 ;i++)
		dist[i] = maxint;
	dist[25] = 0;//Z

	
	int tovisit = 25;
	
	for (int m = 1; m<=p ;m++)
	{
		
		visit[tovisit] = 1;
		node* pp = adjlist[tovisit];
		//update / relaxation
		while (pp)
		{
			
			if (dist[tovisit]+pp->weight<dist[pp->name])
			{
				dist[pp->name] = dist[tovisit]+pp->weight;
			}
			pp = pp->next;
			
		}
		//find next node to visit using a loop 
		//instead a minimum queue
		
		int min_in_row = maxint;
		for(int i = 0 ; i<52 ; i++)
		{

			if (!visit[i] && dist[i]<min_in_row)
			{
				tovisit = i;
				
				min_in_row = dist[i];
				
			}
			
		}

		
	}

	int res = maxint;
	int ii;
	for (int i = 0 ; i<25 ; i++) 
	{
		if (dist[i]<res)
		{
			res = dist[i];
			ii = i;
		}
	}
	char c = 'A'+ii;
	fout<<c<<' '<<dist[ii]<<endl;
	fin.close();
	fout.close();
	return 0;
}

gistfile2.txt