hd 2112 HDU Today

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

xiasha westlake

xiasha station 60

xiasha ShoppingCenterofHangZhou 30

station westlake 20

ShoppingCenterofHangZhou supermarket 10

xiasha supermarket 50

supermarket westlake 10

-1

Sample Output

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

spfa算法：

 #include <stdio.h>

 #include <string.h>

 #include <queue>

 #define inf 0x3f3f3f3f

 #define N 1000000

 using namespace std;

 int vis[], dis[], head[];

 int n, cnt, k;

 char s1[], s2[];

 char sta[][];

 struct note

 {

     int from, to, cost, next;

 }edge[N];

 void add(int x, int y, int z)

 {

     note e = {x, y, z, head[x]};

     edge[cnt] = e;

     head[x] = cnt++;

 }

 void spfa()

 {

     queue<int>q;

     memset(vis, , sizeof(vis));

     memset(dis, inf, sizeof(dis));

     q.push();

     vis[] = ;

     dis[] = ;

     while(!q.empty())

     {

         int u = q.front();

         q.pop();

         vis[u] = ;

         for(int i = head[u]; i != -; i = edge[i].next)

         {

             int v = edge[i].to;

             if(dis[v] > dis[u] + edge[i].cost)

             {

                 dis[v] = dis[u] + edge[i].cost;

                 if(!vis[v])

                 {

                     vis[v] = ;

                     q.push(v);

                 }

             }

         }

     }

     if(dis[] == inf)

         printf("-1\n");

     else

         printf("%d\n", dis[]);

 }

 int main()

 {

     int a, b, c;

     while(~scanf("%d", &n), n != -)

     {

         int flag;

         k = , cnt = ;

         scanf("%s%s", sta[], sta[]);

         memset(head, -, sizeof(head));

         for(int i = ; i < n; i++)

         {

             scanf("%s%s%d", s1, s2, &c);

             flag = ;

             for(int i = ; i <= k; i++)

             {

                 if(strcmp(s1, sta[i]) == )

                 {

                     flag = ;

                     a = i;

                     break;

                 }

             }

             if(flag)

             {

                 strcpy(sta[++k], s1);

                 a = k;

             }

             flag = ;

             for(int i = ; i <= k; i++)

             {

                 if(strcmp(sta[i], s2) == )

                 {

                     b = i;

                     flag = ;

                     break;

                 }

             }

             if(flag)

             {

                 strcpy(sta[++k], s2);

                 b = k;

             }

             add(a, b, c);

             add(b, a, c);

         }

         if(strcmp(sta[], sta[]) == )

         {

             printf("0\n");

             continue;

         }

         spfa();

     }

     return ;

 }

floyd算法：

 #include <stdio.h>

 #include <string.h>

 #define INF 0x3f3f3f3f

 #define N 160

 int dis[N][N];

 int n;

 char s1[], s2[], str[][];

 void init()

 {

     for(int i = ; i < N; i++)

     for(int j = ; j < N; j++)

     {

         if(j == i)

             dis[i][j] = ;

         else

             dis[i][j] = INF;

     }

 }

 int min(int x, int y)

 {

     return x < y ? x : y;

 }

 void floyd()

 {

     for(int k = ; k < N; k++)

     for(int i = ; i < N; i++)

     {

         if(dis[i][k] != INF)

         {

             for(int j = ; j < N; j++)

             dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

         }

     }

 }

 int main()

 {

     while(~scanf("%d", &n), n != -)

     {

         int k = , a, b, t, flag;

         init();

         scanf("%s%s", s1, s2);

         strcpy(str[], s1);

         strcpy(str[], s2);

         while(n--)

         {

             scanf("%s%s%d", s1, s2, &t);

             flag = ;

             for(int i = ; i <= k; i++)

             {

                 if(strcmp(str[i], s1) == )

                 {

                     flag = ;

                     a = i;

                     break;

                 }

             }

             if(flag)

             {

                 strcpy(str[++k], s1);

                 a = k;

             }

             flag = ;

             for(int i = ; i <= k; i++)

             {

                 if(strcmp(str[i], s2) == )

                 {

                     flag = ;

                     b = i;

                     break;

                 }

             }

             if(flag)

             {

                 strcpy(str[++k], s2);

                 b = k;

             }

             dis[a][b] = dis[b][a] = t;

         }

         floyd();

         if(strcmp(str[], str[]) == )

         {

             printf("0\n");

             continue;

         }

         if(dis[][] != INF)

             printf("%d\n", dis[][]);

         else

             printf("-1\n");

     }

     return ;

 }

巴特西

hd 2112 HDU Today

最新文章

热门文章