1 原题中文大意;
Sicily 1031 Campus实际上就是求一个图中给出两点的最短路径的问题。
2 算法思想及解题用到的主要数据结构;
用 dijkstra 算法求给定两点的最短路径.
按路径长度递增次序产生最短路径算法： 把V分成两组： （1）S：已求出最短路径的顶点的集合 （2）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中， 保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。
3 逐步求精算法描述
用邻接矩阵存放图.1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值 若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 若不存在<V0,Vi>，d(V0,Vi)为∝ 2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S 3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的 距离值比不加W的路径要短，则修改此距离值 重复上述步骤2、3，直到S中包含所有顶点，即S=T为止
3 程序注释清单 // 这份代码通不过sicily。有case错误。我实在找不到原因。
#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;
}
4 对时间复杂度，空间复杂度方面的分析、估算。
时间复杂度和空间复杂度都是O(n*n). http://ykyi.net
///////////// 原题
1031. Campus
Description
At present, Zhongshan University has 4 campuses with a total area of 6.17 square kilometers sitting respectively on both sides of the Pearl River or facing the South China Sea. The Guangzhou South Campus covers an area of 1.17 square kilometers, the North Campus covers an area of 0.39 square kilometers, the Guangzhou East Campus has an area of 1.13 square kilometers and the Zhuhai Campus covers an area of 3.48 square kilometers. All campuses have exuberance of green trees, abundance of lawns and beautiful sceneries, and are ideal for molding the temperaments, studying and doing research.
Sometime, the professors and students have to go from one place to another place in one campus or between campuses. They want to find the shortest path between their source place S and target place T. Can you help them?
Input
The first line of the input is a positive integer C. C is the number of test cases followed. In each test case, the first line is a positive integer N (0<N<=100) that represents the number of roads. After that, N lines follow. The i-th(1<=i<=N) line contains two strings Si, Ti and one integer Di (0<=Di<=100). It means that there is a road whose length is Di between Si and Ti. Finally, there are two strings S and T, you have to find the shortest path between S and T. S, T, Si(1<=i<=N) and Ti(1<=i<=N) are all given in the following format: str_Campus.str_Place. str_Campus represents the name of the campus, and str_Place represents the place in str_Campus. str_Campus is "North", "South", "East" or "Zhuhai". str_Place is a string which has less than one hundred lowercase characters from "a-z". You can assume that there is at most one road directly between any two places.
Output
The output of the program should consist of C lines, one line for each test case. For each test case, the output is a single line containing one integer. If there is a path between S and T, output the length of the shortest path between them. Otherwise just output "-1" (without quotation mark). No redundant spaces are needed.