程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU-2112-最短路（map）

HDU-2112-最短路（map）

編輯：C++入門知識

HDU-2112-最短路（map）

HDU Today

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14031 Accepted Submission(s): 3279

Problem Description 經過錦囊相助，海東集團終於度過了危機，從此，HDU的發展就一直順風順水，到了2050年，集團已經相當規模了，據說進入了錢江肉絲經濟開發區500強。這時候，XHD夫婦也退居了二線，並在風景秀美的諸暨市浬浦鎮陶姚村買了個房子，開始安度晚年了。
這樣住了一段時間，徐總對當地的交通還是不太了解。有時很郁悶，想去一個地方又不知道應該乘什麼公交車，在什麼地方轉車，在什麼地方下車（其實徐總自己有車，卻一定要與民同樂，這就是徐總的性格）。
徐總經常會問蹩腳的英文問路：“Can you help me?”。看著他那迷茫而又無助的眼神，熱心的你能幫幫他嗎？
請幫助他用最短的時間到達目的地（假設每一路公交車都只在起點站和終點站停，而且隨時都會開）。

Input 輸入數據有多組，每組的第一行是公交車的總數N(0<=N<=10000)；
第二行有徐總的所在地start，他的目的地end；
接著有n行，每行有站名s，站名e，以及從s到e的時間整數t(0 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

這道題目就是一道裸的最短路問題，但是這裡有個棘手的地方就是，地名都是用字符串表示，而不像我們平時做的題目用數字來表示。所以我們需要用到map函數來巧妙地處理這個問題。
我用的是dijkstra算法+鄰接表做的。代碼如下： 
//dijkstra算法
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int max_d=150+5;
const int max_n=99999999;
const int max_G=150+5;
struct Edge{
    int to,dis;
    Edge(int to,int dis){
        this -> to = to;
        this -> dis = dis;
    }
};

mapm;
vectorG[max_G];
typedef pairP;

int n,t,pot;
int d[max_d];
char ss[100],sss[100];
char s1[100],s2[100];

void dijkstra()
{
    priority_queue,greater >q;
    fill(d+1,d+pot+1,max_n);
    while(q.size()) q.pop();
    d[1]=0;
    q.push(P(0,1));
    while(q.size()){
        P p=q.top(); q.pop();
        int v=p.second;
        if(d[v]d[v]+e.dis){
                d[e.to]=d[v]+e.dis;
                q.push(P(d[e.to],e.to));
            }
        }
    }if(d[2]==max_n) printf("-1\n");
    else             printf("%d\n",d[2]);
}
int main()
{
    while(scanf("%d",&n)!=EOF){

        if(n==-1) break;
        m.clear();            //初始化map
        for(int i=0;i<155;i++)
            G[i].clear();     //初始化鄰接表
        scanf("%s%s",ss,sss);
        m[ss]=1; m[sss]=2;
        pot=2;
        for(int i=0;i