学习不停止，金钱永不眠
# Ethernet header contains a type fileld of 0x0800, which identifies the frame as an IPv4 frame.
# 若支持dual-stack的server既有IPv4又有IPv6。则IP层让server透明地既可处理IPv4又可处理IPv6.该server需要绑定到wildcard且未设置IPV6_V6ONLY socket option.
# UNP Page359 Figure 12.5 Summary of interoperability between IPv4 and IPv6 clients and servers.
# 尽可能用IPv6, since an IPv6 client can still communicate with IPv4 servers, and vice versa.
# gethostbyname 和 gethostbyaddr 用来在 IPv4 地址和 hostname 之间转换. getservbyport 和 getservbyname 则是与服务相关。gethostbyname出错时不设errno而是设h_errno，并有hstrerror()函数。
# FQDN的全称是: Fully Qualified domain name. 技术上说必须以点号(period)终止.
# AAAA 被称为 "quad A" rcord, 给出了从hostname到Ipv6地址的映射。 PTR用来把IP地址到hostname.
# Entries in the DNS are known as Resource Records(RRs).
# 一个点分十进制(dotted-decimal)IPv4的地址前加 0::ffff:就是 IPv6的字符串形式。
# 与getpeername对应的函数不是gethostname而是getsockname.
# getaddrinfo函数的host参数指定为dotted-decimal IPv4或 IPv6 hex string,会使得只有IPv4或IPv6的addrinfo返回。
# 不给UDP套接字设置SO_REUSEADDR选项。We do not set the SO_REUSEADDR socket option for the UDP socket because this socket option can allow multiple sockets to bind the same UDP port on hosts that support multicasting. Since there is nothing like TCP's TIME_WAIT state for a UDP socket, there is no need to set this socket option when the server is started.
# 一般情况下，同端口的不同协议对应同样的服务。但也有例外。对于端口514，which is the rsh service with TCP, but the syslog service with UDP.
# gethostbyaddr的第一个参数是char* addr，而其实它并非指向一个char* 事实上指向in_addr结构体。
# getaddrinfo好复杂呀！hint的ai_flags设置了AI_CONONNAME成员得到host的canonical name.
# port 53 是domain service的端口号.
# 如果设置了IPV6_V6ONLY.那么一个来自ipv4 client的连接会被拒绝。
# POSIX says that specifying AF_UNSPEC will return addresses that can be used with any protocol family that can be used with the hostname and service name.
# POSIX specification also implies that if the AI_PASSIVE flag is specified without a hostname, then the IPv6 wildcard address(IN6ADDR_ANY_INIT or 0::0) should be returned as a sockaddr_in6 structure, along with the IPv4 wildcard address(INADDR_ANY or 0.0.0.0), which is returned as a sockaddr_in structure.
# An ipv6 server socket can handle both ipv4 and ipv6 on a dual-stack host. Refer to page319 in UNP for details.
好复杂好深奥的数学变换。本次讲座的收获也就是让我一定程度上开拓了视野，接触到N多电信方面的术语。小波变换，脏纸编码，数字水印之类。术业有专功，我要专功我的Linux去嘞。。。
#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;
}