HDU 2112 HDU Today （最短路(dijkstra邻接矩阵) + hash + 2分）

HDU 2112 HDU Today （最短路(dijkstra邻接矩阵) + hash + 二分）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2112

Description:

经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。

Input:

输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。

Output:

如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。

Sample Input:

6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1

Sample Ouput:

代码及代码解析如下：

/*
  Name: 最短路(dijkstra邻接矩阵)+hash判重并统计顶点数+二分查找返回顶点位置 
  Copyright: 
  Author: Kesha
  Date: 14/05/12 20:57
  Description: 注意：起始点和终点不在给出的路线中的情况！！！ 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
#include <iomanip>
#include <algorithm>
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

const int S = 163; 
const int N = 155;
const int M = 12000;
const int MAX = 1000000000; 

char names[N][35], sName[35], eName[35];
int dis[N], sumVs, map[N][N], n;

struct edge {
	char u[35];
	char v[35];
	int w;
}e[M];

bool vis[N];

struct node //hash表相关数据信息
{ 
	char str[35];
	node *next;
	node(char *ch, node *p) {
		strcpy(str, ch);
		next = p;
	}
};

struct hash 
{
	node *link;
}hashTable[S];

void initHashTable() //hash表初始化 
{
	for (int i=0; i<S; ++i) hashTable[i].link = NULL;
	return ;
}

unsigned int BKDRHash(char *str) //hash
{
	unsigned int seed = 131;
	unsigned int hash = 0;
	while (*str) hash = hash * seed + (*str++);
	return hash & 0x7FFFFFFF;
}

void insertAndFind(char *str) //hash表中插入与查找 
{
	int k = BKDRHash(str) % S;
	node *p = hashTable[k].link;
	while (p) {
		if (!strcmp(p->str, str)) return ;
		p = p->next;
	}
	node *q = new node(str, NULL);
	q->next = hashTable[k].link;
	hashTable[k].link = q;
	strcpy(names[sumVs++], str);
	return ;
}

void del(node *p) //释放哈希表所占内存 
{
	if (!p) return ;
	del(p->next);
	delete p;
}

int cmp(const void *a, const void *b) 
{
	return (strcmp((char *)a, (char *)b));
}

int binarySearch(char *str) //二分查找定位顶点位置 
{
	int left = 0;
	int right = sumVs;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (!strcmp(names[mid], str)) return mid;
		if (strcmp(names[mid], str) > 0) right = mid - 1;
		else left = mid + 1;
	}
	return -1;//起始点或终点不在二分查找表中是返回-1 
}

void init(int vs) {//邻接矩阵初始化 
	for (int i=0; i<vs-1; ++i) {
		map[i][i] = 0;
		for (int j=i+1; j<vs; ++j)	map[i][j] = map[j][i] = MAX;
	}
	return ;
}

void dijkstra(int vs, int s) //最短路 
{
	memset(vis, false, sizeof(vis));
	int pos = s;
	vis[pos] = true;
	for (int i=0; i<vs; ++i) dis[i] = map[pos][i];
	dis[pos] = 0;
	int minLen;
	for (int i=1; i<vs; ++i) {
		pos = s;
		minLen = MAX;
		for (int j=0; j<vs; ++j) {
			if (!vis[j] && minLen>dis[j]) minLen = dis[j], pos = j;
		} 
		vis[pos] = true;
		for (int j=0; j<vs; ++j) {
			int len = dis[pos] + map[pos][j];
			if (!vis[j] && dis[j]>len) dis[j] = len;	
		}
	}
	return ;
}

int main() 
{
	while (~scanf("%d", &n), n!=-1) {
		scanf("%s %s", sName, eName);
		sumVs = 0;
		initHashTable();
		for (int i=0; i<n; ++i) {
			scanf ("%s%s%d", e[i].u, e[i].v, &e[i].w);
			insertAndFind(e[i].u); //插入hash表 
			insertAndFind(e[i].v); //插入hash表 
		}
		qsort(names, sumVs, sizeof(names[0]), cmp);
		init(sumVs);
		for (int i=0; i<n; ++i) {
			int u = binarySearch(e[i].u); //对每条线路的起始点和终点返回顶点位置 
			int v = binarySearch(e[i].v); 
			if (map[u][v] > e[i].w) map[u][v] = map[v][u] = e[i].w;//判重，选最小者 
		}
		int s = binarySearch(sName);
		int t = binarySearch(eName);
		if (s==-1 || t==-1) {  //起点或终点不在二分查找表中 
			printf ("-1\n");
			continue;
		}
		dijkstra(sumVs, s);
		if (dis[t] == MAX) printf ("-1\n");
		else printf ("%d\n", dis[t]);
		for (int i=0; i<S; ++i) del(hashTable[i].link);
	}
	return 0;
}

HDU 2112 HDU Today （最短路(dijkstra邻接矩阵) + hash + 2分）

相关推荐