HDU-2112 HDU Today-白红宇

HDU-2112 HDU Today

阅读量：4123 次

发布时间：2019-05-25

本文共 1906 字，大约阅读时间需要 6 分钟。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          using namespace std;const int maxn = 1e6;const int INF = 1e8;int n, num, pos, ans;string Start, End;map
          
            number;int connect[maxn];int sign[maxn];int dis[maxn];struct node{ int next; int to; int len;} edge[maxn];inline void code(string temp){ if(!number.count(temp)) { number[temp] = num; num ++; }}inline void add_edge(string a, string b, int len){ int x = number[a]; int y = number[b]; edge[pos].to = y; edge[pos].len = len; edge[pos].next = connect[x]; connect[x] = pos; pos ++;}void SPFA(){ queue
           
             process; int op = number[Start]; int ed = number[End]; memset(sign, 0, sizeof(sign)); for(int i = 0; i < maxn; i ++) dis[i] = INF; dis[op] = 0; process.push(op); sign[op] = 1; while(!process.empty()) { int next_op = process.front(); process.pop(); sign[next_op] = 0; for(int i = connect[next_op]; i != -1; i = edge[i].next) { int next_ed = edge[i].to; int next_len = edge[i].len; if(dis[next_op] + next_len < dis[next_ed]) { dis[next_ed] = dis[next_op] + next_len; if(!sign[next_ed]) { process.push(next_ed); sign[next_ed] = 1; } } } } ans = dis[ed];}int main(){ num = 0; while(~scanf("%d", & n)) { if(n == -1) break; memset(connect, -1, sizeof(connect)); cin >> Start; code(Start); cin >> End; code(End); pos = 0; for(int i = 0; i < n; i ++) { string a, b; int len; cin >> a; code(a); cin >> b; code(b); cin >> len; add_edge(a, b, len); add_edge(b, a, len); } SPFA(); if(ans < INF) printf("%d\n", ans); else printf("-1\n"); } return 0;}

题意：

想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车，请帮助他用最短的时间到达目的地。

题解：

练习SPFA。就是多了一个map将 string 用 int 代替。

一开始我判断是否输出-1时是这样判断：

if(dis[ed] < INF)

return ans = dis[ed];

else

return 0;

…

if(SPFA())

cout << ans << endl;

else

cout << “-1” << endl;

错在当初始位置和末尾相同的时候 dis[ed] = 0，会return 0而输出-1。还有就是对string进行编号的时候，num要写在最外边，使地点单词与数字一一对应。

转载地址：http://vctpi.baihongyu.com/

你可能感兴趣的文章