Hotel booking(spfa+floyd)

http://acm.hdu.edu.cn/showproblem.php?pid=2992

题意：有n个城市，编号为（1~n），有一些城市中有一些旅店，要求从一个城市到另一个城市不能超过10小时，问能否从1号城市到n号城市，如果能需要住的最少的旅店数目是多少。

思路：首先将1号城市和n号城市置为有旅店的城市，spfa求每个旅店到其它旅店的最短距离，如果距离小于10小时，将两个旅店之间的权值置为1，这样就能构造出所有旅店之间的图，然后对该图利用floyd求最短路。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <queue>
  5 #include <vector>
  6 const int N=10005;
  7 const int INF=1<<28;
  8 using namespace std;
  9 
 10 struct node
 11 {
 12     int v,w;
 13     node(int v,int w):v(v),w(w) {}
 14 };
 15 vector<node>vv[N];
 16 int mp[120][120],id[N];
 17 int a[N],dis[N];
 18 bool vis[N];
 19 int hotel,n;
 20 void init()
 21 {
 22     memset(id,0,sizeof(id));
 23     for (int i = 0; i <= hotel+2; i++)
 24     {
 25         for (int j = 0; j <= hotel+2; j++)
 26         {
 27             mp[i][j] = INF;
 28         }
 29         mp[i][i] = 0;
 30     }
 31     for (int i = 0; i <= n; i++)
 32         vv[i].clear();
 33 }
 34 void spfa(int s)
 35 {
 36     queue<int>q;
 37     memset(vis,0,sizeof(vis));
 38     for (int i = 0; i <= n; i++)
 39         dis[i] = INF;
 40     dis[s] = 0;
 41     q.push(s);
 42     vis[s] = true;
 43     while(!q.empty())
 44     {
 45         int u = q.front();
 46         q.pop();
 47         vis[u] = false;
 48         for (int i = 0; i < (int)vv[u].size(); i++)
 49         {
 50             int v = vv[u][i].v;
 51             int w = vv[u][i].w;
 52             if(dis[v]>dis[u]+w)
 53             {
 54                 dis[v] = dis[u]+w;
 55                 if(!vis[v])
 56                 {
 57                     q.push(v);
 58                     vis[v] = true;
 59                 }
 60             }
 61         }
 62     }
 63     for (int i = 1; i <= n; i++)
 64     {
 65         if (dis[i]<=600)
 66             mp[id[s]][id[i]] = 1;
 67     }
 68 }
 69 void floyd()
 70 {
 71     for (int k = 0; k <= hotel+1; k++)
 72     {
 73         for (int i = 0; i <= hotel+1; i++)
 74         {
 75             for (int j = 0; j <= hotel+1; j++)
 76                 if(mp[i][j] > mp[i][k]+mp[k][j])
 77                     mp[i][j] = mp[i][k]+mp[k][j];
 78         }
 79     }
 80 }
 81 int main()
 82 {
 83     while(scanf("%d",&n)&&n)
 84     {
 85         scanf("%d",&hotel);
 86         init();
 87         for (int i = 1; i <= hotel; i++)
 88         {
 89             scanf("%d",&a[i]);
 90             id[a[i]] = i;
 91         }
 92         a[0] = 1;
 93         a[hotel+1] = n;
 94         id[1] = 0;
 95         id[n] = hotel+1;
 96         int m,u,v,w;
 97         scanf("%d",&m);
 98         for (int i = 1; i <= m; i++)
 99         {
100             scanf("%d%d%d",&u,&v,&w);
101             vv[u].push_back(node(v,w));
102             vv[v].push_back(node(u,w));
103         }
104         for (int i = 0; i <= hotel; i++)
105             spfa(a[i]);
106         floyd();
107         if (mp[0][hotel+1]>=INF)
108             puts("-1");
109         else
110             printf("%d
",mp[0][hotel+1]-1);
111     }
112     return 0;
113 }

View Code