2013
12-29

# HDU Today

note：一组数据中地名数不会超过150个。

note：一组数据中地名数不会超过150个。

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

50

Hint:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake

**和**从此还是过上了幸福的生活。

��全剧终��

#include<map>
#include<string>
#include<iterator>
#include<iostream>
#include<algorithm>
using namespace std;

map<string, int> treeMap;
map<string, int>::iterator mapIter1;
map<string, int>::iterator mapIter2;
const int inf = 1000000;
const int Size = 160;

bool vis[Size];
int dist[Size];
int cost[Size][Size];

void Dijkstra(int v, int w, int n)
{
int i,j;
int u;
int min;

for(i = 1; i <= n; i ++)
{
dist[i] = cost[v][i];
vis[i] = false;
}

vis[v] = true;
dist[v] = 0;

for(i = 2; i <= n; i ++)
{
min = inf;
for(j = 1; j <= n; j ++)
if(!vis[j] && min > dist[j])
{
min = dist[j];
u = j;
}

vis[u] = true;

for(j = 1; j <= n; j ++)
if(!vis[j] && dist[j] > dist[u] + cost[u][j])
dist[j] = dist[u] + cost[u][j];
}

if(dist[w] == inf)
cout << "-1" << endl;
else
cout << dist[w] << endl;
}

int main()
{
int sp;
int num;
int len;
int i,j;
int cnt = 0;
string start,destination;
string begin,end;

while(true)
{
cin >> num;

if(num == -1)
break;

sp = 0;
cnt = 0;
treeMap.clear();

cin >> start >> destination;
if(!treeMap[start])
{
cnt ++;
treeMap[start] = cnt;
}
if(!treeMap[destination])
{
cnt ++;
treeMap[destination] = cnt;
}

for(i = 0; i < Size; i++)
for(j = 0; j < Size; j++)
if(i == j)
cost[i][j] = 0;
else
cost[i][j] = inf;

for(i = 1; i <= num; i ++)
{
cin >> begin >> end;
if(!treeMap[begin])
{
cnt ++;
treeMap[begin] = cnt;
}
if(!treeMap[end])
{
cnt ++;
treeMap[end] = cnt;
}

cin >> len;
cost[treeMap[end]][treeMap[begin]] = cost[treeMap[begin]][treeMap[end]] = len;
}

Dijkstra(treeMap[start], treeMap[destination], treeMap.size());
}

return 0;
}

1. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯

2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.