#include <map>#include <vector>
#include <string>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cassert>
#define INFINITE 0x0FFFFFFF
// 这个类的函数几乎不做参数有效性的检查.
class graph_t
{
public:
// 构建一个 num x num 的邻接矩阵
graph_t(int num)
{
m_matrix = new int[num*num];
m_sunit = new bool[num];
m_spath_table = new int[num];
// memset(m_matrix, INFINITE, num*num); // INFINITE 表示无穷远.
for ( int i = 0; i < num*num; i++ )
{
m_matrix[i] = INFINITE;
}
m_num = num;
}
// row,column 取 [0, m_num)
int& operator()(int row, int column)
{
return m_matrix[row * m_num + column];
}
// vtx_start, vtx_end 取 [vtx_start, vtx_end)
int shortestpath_dij(int vtx_start, int vtx_end)
{
init_dij(vtx_start); // 初始化dijkstra算法需要的一些数据.
if ( vtx_end == vtx_start )
{
return this->operator()(vtx_start, vtx_end);
}
// 还剩 m_num - 1 个点.
for ( int i = 1; i < m_num; i++ )
{
// 找下一个最近的点.
int vtx = -1, min = INFINITE;
for ( int j = 0; j < m_num; j++ )
{
if ( m_sunit[j] ) // 这个点已经在已经求得最短路径的点的集合中了.
continue;
if ( m_spath_table[j] < min )
{
vtx = j;
min = m_spath_table[j];
}
}
// 已经没有连通的顶点了.
if ( vtx == -1 )
{
return -1;
}
m_sunit[vtx] = true; // 把这个点加入集合中.
// 这个点是终点. http://ykyi.net
if ( vtx == vtx_end )
{
return min;
}
// 因为找到了一个新的点加入了集合，更新最短路径表.
for ( int k = 0; k < m_num; k++ )
{
if ( m_sunit[k] )
continue;
if ( min + this->operator()(vtx, k) < m_spath_table[k] )
{
m_spath_table[k] = min + this->operator()(vtx, k);
}
}
}
assert(0); // it's not suppossed to reach here.
return -1;
}
~graph_t()
{
delete m_matrix;
delete m_sunit;
delete m_spath_table;
}
private:
void init_dij(int vtx_start)
{
memset(m_sunit, 0, m_num); // 初始化为没有点加入这个已求得最短路径的终点集合.
for ( int i = 0; i < m_num; i++ )
{
m_spath_table[i] = this->operator()(vtx_start, i);
}
assert( 0 == m_spath_table[vtx_start] );
m_sunit[vtx_start] = true;
}
private:
int m_num;
int* m_matrix; // 存邻接矩阵
bool* m_sunit; // 在dijkstra计算过程中用来存某点是否已经是最短路径中的点.
int* m_spath_table; // 在dijkstra计算过程中存到某点是的最短路径是多少.
};
int main(int argc, char* argv[])
{
int case_count, path_count, weight, next_ava_vtx;
int vtx_start, vtx_end;
std::map<std::string, int> loc2vtx; // 存地点字符串到图的顶点号的映射.
std::vector<int> spirit;
std::string line;
std::cin >> case_count;
for ( int i = 0; i < case_count; i++ )
{
loc2vtx.clear();
spirit.clear();
next_ava_vtx = 0;
std::cin >> path_count;
for ( int j = 0; j < path_count; j++ )
{
// 得到起点地址字符串.
std::cin >> line;
std::map<std::string, int>::iterator ite = loc2vtx.find(line);
if ( loc2vtx.end() != ite )
{
vtx_start = ite->second;
}
else
{
vtx_start = next_ava_vtx;
loc2vtx[line] = vtx_start;
next_ava_vtx++;
}
spirit.push_back(vtx_start);
// 得到终点地址字符串.
std::cin >> line;
ite = loc2vtx.find(line);
if ( loc2vtx.end() != ite )
{
vtx_end = ite->second;
}
else
{
vtx_end = next_ava_vtx;
loc2vtx[line] = vtx_end;
next_ava_vtx++;
}
spirit.push_back(vtx_end);
// 得到权重
std::cin >> weight;
spirit.push_back(weight);
}
// 至此 next_ava_vtx 中存放的实际上是邻接方阵的阶.
graph_t graph(next_ava_vtx);
for ( int i = 0; i < spirit.size()/3; i++ )
{
int x = spirit[3*i];
int y = spirit[3*i+1];
int w = spirit[3*i+2];
graph(x, y) = w;
graph(y, x) = w;
}
for ( int i = 0; i < next_ava_vtx; i++ )
{
graph(i, i) = 0;
}
std::cin >> line;
std::map<std::string, int>::iterator ite = loc2vtx.find(line);
if ( ite == loc2vtx.end() )
{
std::cout << “-1\n”;
continue;
}
vtx_start = loc2vtx[line];
std::cin >> line;
ite = loc2vtx.find(line);
if ( ite == loc2vtx.end() )
{
std::cout << “-1\n”;
continue;
}
vtx_end = loc2vtx[line];
if ( vtx_start == vtx_end )
{
std::cout << “0\n”;
continue;
}
std::cout << graph.shortestpath_dij(vtx_start, vtx_end) << std::endl;
}
return 0;
}