学步园

       这题做得无比纠结~~~WA了无数次，一开始以为算法错了， 调了半天发现不了问题， 最后还是看别人解题报告才过，

原来当输入的S和T不在列表且S=T时，是要输出0的，这个要注意~~

      主要是用一个map把字符串映射到数字

#include <iostream>
#include <string>
#include <map>
#include <memory.h>
#define INF 1000000
#define MAX 210
using namespace std;

int cost[MAX][MAX];
int my_distance[MAX];
bool isvisit[MAX];

int n;
int edge_count;

void shortest_path(int);
int main()
{
	int cases;
	int  start, goal;
	string a, b;
	int distance;

	int count;
	map<string, int> name;
	map<string, int>::iterator iter1, iter2;

	cin >> cases;
	while (cases--)
	{

		cin >> n;

		for (int i = 0; i < MAX; i++)
			for (int j = 0; j < MAX; j++)
				if (i != j) cost[i][j] = INF;
				else cost[i][j] = 0;

		count = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> a >> b >> distance;
			iter1 = name.find(a);
			iter2 = name.find(b);
			if (iter1 != name.end() && iter2 != name.end())
			{
				cost[iter1->second][iter2->second] = distance;
				cost[iter2->second][iter1->second] = distance;
			}
			else if (iter1 == name.end() && iter2 == name.end())
			{
				if (a != b)
				{
					cost[count][count+1] = distance;
					cost[count+1][count] = distance;
					name.insert(pair<string, int>(a, count++));
					name.insert(pair<string, int>(b, count++));
				}
				else
				{
					cost[count][count] = distance;
					name.insert(pair<string, int>(a, count++));
				}

			}
			else if (iter1 == name.end() && iter2 != name.end())
			{
				cost[count][iter2->second] = distance;
				cost[iter2->second][count] = distance;
				name.insert(pair<string, int>(a, count++));
			}
			else 
			{
				cost[count][iter1->second] = distance;
				cost[iter1->second][count] = distance;
				name.insert(pair<string, int>(b, count++));
			}
		}

		edge_count = count;
		cin >> a >> b;
		iter1 = name.find(a);
		iter2 = name.find(b);

		if (iter1 != name.end() && iter2 != name.end())
		{
			start =(name.find(a))->second;
			goal = (name.find(b))->second;

			shortest_path(start);

			if (my_distance[goal] < INF)
				cout << my_distance[goal] << endl;
			else
				cout << "-1" << endl;

		}
		else if (a == b)
			cout << "0" << endl;
		else
			cout << "-1" << endl;

		name.clear();
	}
	return 0;
}

void shortest_path(int start)
{
	memset(isvisit, false, sizeof(isvisit));

	for (int i = 0; i < edge_count; i++)
		my_distance[i] = cost[start][i];

	isvisit[start] = true;
	int _min = INF, min_point;
	int next;

	for (int i = 0; i < edge_count-1; i++)
	{
		_min = INF;
		for (int j = 0; j < edge_count; j++)
			if (!isvisit[j] && _min > my_distance[j])
			{
				_min = my_distance[j];
				min_point = j;
			}

		isvisit[min_point] = true;

		for (int j = 0; j < edge_count; j++)
			if (!isvisit[j] && my_distance[j] > cost[min_point][j] + my_distance[min_point])
				my_distance[j] =  cost[min_point][j] + my_distance[min_point];

	}
}