題干：

HDU Today

Time Limit : 15000/5000ms (Java/Other)???Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 11???Accepted Submission(s) : 5

Problem 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 Output

50

Hint: The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake 雖然偶爾會迷路，但是因為有了你的幫助 **和**從此還是過上了幸福的生活。 ――全劇終――

解題報告：

? ? 幾乎裸題單源最短路，加一個判斷兩者是否可達即可。（可用并查集也可用dis[v] = INF）

? ? 字符串用map映射成一個整數即可。

AC代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<iostream> using namespace std; const int MAX = 100000 + 5; const int INF = 0x3f3f3f3f ; map<string,int> mp; struct Node {int to;int w;int ne; // bool operator <(const Node & b) const { // return w>b.w; // } } e[MAX];struct point {int pos;int c;point(){}//沒有此構造函數不能寫 node t 這樣point(int pos,int c):pos(pos),c(c){}//可以寫node(pos,cost)這樣bool operator <(const point & b) const {return c>b.c;} };int head[MAX]; int vis[MAX]; int cnt = 0; int n,m; int top = -1; int dis[MAX];//表示從出發點開始到該點的最短距離。 void add(int u,int v,int w) {e[cnt].to = v;e[cnt].w = w;e[cnt].ne = head[u];head[u] = cnt;cnt++; } void Dijkstra(int u,int v) {priority_queue<point> pq; dis[u] = 0;point cur = point(u,0);pq.push(cur); // vis[u] = 1;while(!pq.empty()) {point now = pq.top();pq.pop();if(vis[now.pos] == 1) continue;vis[now.pos] = 1;if(now.pos == v) break;//不把這一步放到 if(vis[now.pos] == 1) continue; 的原因是：要記錄成v也是走過的，這樣方便統一。 for(int i = head[now.pos]; i!=-1; i=e[i].ne) {if( dis[e[i].to] > dis[now.pos] + e[i].w ) {dis[e[i].to] = dis[now.pos] + e[i].w;pq.push(point(e[i].to,dis[e[i].to] ) ); }} }if(dis[v] == INF) {printf("-1\n");}else printf("%d\n",dis[v]);} void init() {cnt = 0;top = -1;mp.clear();memset(head,-1,sizeof(head) );memset(dis,INF,sizeof(dis) ) ;memset(vis,0,sizeof(vis) ) ; } int main() {int a,b,w;char st[40],ed[40];char u[40],v[40];while(~scanf("%d",&n) ) {if(n == -1) break;init();scanf("%s %s",st,ed);if(mp.find(st) == mp.end() ) mp[st] = ++top;if(mp.find(ed) == mp.end() ) mp[ed] = ++top;for(int i = 1; i<=n; i++) {scanf("%s %s %d",&u,&v,&w);if(mp.find(u) == mp.end() ) mp[u] = ++top;if(mp.find(v) == mp.end() ) mp[v] = ++top;add(mp[u],mp[v],w);add(mp[v],mp[u],w);}Dijkstra(mp[st],mp[ed]);//或者 Dijkstra(0,1)}return 0 ;}

總結

以上是生活随笔為你收集整理的【HDU - 2112】 HDU Today（dijkstra单源最短路 + map转换）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。