首页 > ACM题库 > HDU-杭电 > HDU 2992-Hotel booking -最短路径-[解题报告]HOJ
2014
02-24

HDU 2992-Hotel booking -最短路径-[解题报告]HOJ

Hotel booking

问题描述 :

A transport company often needs to deliver goods from one city to another city. The transport company has made a special deal with a hotel chain which allows its drivers to stay in the hotels of this chain for free. Drivers are only allowed to drive up to 10 hours a day. The transport company wants to find a route from the starting city to the destination city such that a driver can always spend the night in one of the hotels of the hotel chain, and that he needs to drive at most 10 hours from one hotel to the next hotel (or the destination). Of course, the number of days needed to deliver the goods should also be minimized.

输入:

The input file contains several test cases. Each test case starts with a line containing an integer n, (2 ≤ n ≤ 10000), the number of cities to be considered when planning the route. For simplicity, cities are numbered from 1 to n, where 1 is the starting city, and n is the destination city. The next line contains an integer h followed by the numbers c1, c2, …, ch indicating the numbers of the cities where hotels of the hotel chain are located. You may assume that 0 ≤ h ≤ min(n, 100). The third line of each test case contains an integer m (1 ≤ m ≤ 105), the number of roads to be considered for planning the route. The following m lines describe the roads. Each road is described by a line containing 3 integers a, b, t (1 ≤ a, b ≤ n and 1 ≤ t ≤ 600), where a, b are the two cities connected by the road, and t is the time in minutes needed by the driver to drive from one end of the road to the other. Input is terminated by n = 0.

输出:

The input file contains several test cases. Each test case starts with a line containing an integer n, (2 ≤ n ≤ 10000), the number of cities to be considered when planning the route. For simplicity, cities are numbered from 1 to n, where 1 is the starting city, and n is the destination city. The next line contains an integer h followed by the numbers c1, c2, …, ch indicating the numbers of the cities where hotels of the hotel chain are located. You may assume that 0 ≤ h ≤ min(n, 100). The third line of each test case contains an integer m (1 ≤ m ≤ 105), the number of roads to be considered for planning the route. The following m lines describe the roads. Each road is described by a line containing 3 integers a, b, t (1 ≤ a, b ≤ n and 1 ≤ t ≤ 600), where a, b are the two cities connected by the road, and t is the time in minutes needed by the driver to drive from one end of the road to the other. Input is terminated by n = 0.

样例输入:

6
3 2 5 3
8
1 2 400
3 2 80
3 4 301
4 5 290
5 6 139
1 3 375
2 5 462
4 6 300
3
0
2
1 2 371
2 3 230
0

样例输出:

2
-1

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2992

题目大意:有一家物流公司要送货炒年糕起点(1)送到终点(n),途中有n个城市其中只有h家客栈是免费休息的,途中有m条路通向不同的城市,开车的司机每天最多开10个小时的车程,问你起点送货到终点最少需要住几家客栈(规定只能住自家免费客栈)。 如果答案不存在输出-1。

解题思路:

    司机从起点或者休息的客栈出发,落脚点必是下一家休息的客栈或者终点。所以对每家客栈(包括起点)spfa一次,找出客栈间最小车程小于十小时的,如果两件客栈间车程小于10小时则令他们的行走天数g[u][v]为1。  开始把终点也放入spfa了一次,wrong answer了一次。

   注意g[][]初始值赋为无穷大,客栈对应所在的城市用map映射一下(道理同节点离散化一样的),再对包括起点终点在内的所有客栈floyd一次,求出g[start][end]的值。

#include <iostream>
 #include <cstdio>
 #include <map>
 #include <vector>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 const int maxn=10005;
 const int INF=0x3fffffff;
 int que[maxn];
 int st[110];
 int g[110][110];
 int inque[maxn];
 int dis[maxn];
 int n, num;
 
 struct Node
 {
     int v, cost;
     Node(int v_,int cost_)
     {
         v=v_, cost=cost_;
     }
 };
 
 map<int,int>mp;
 vector<Node>vt[maxn];
 
 void spfa(int start)   ///可做模板
 {
     int h=0, t=0;
     for(int i=1; i<=n; i++)
     {
         dis[i]=INF;
         inque[i]=0;
     }
     dis[start]=0;
     inque[start]=1;
     que[t++]=start;
     while(h!=t)
     {
         int u=que[h++];
         inque[u]=0; ///出队列
         if(h==maxn) h=0;  ///!循环队列
         for(int i=0; i<vt[u].size(); i++)
         {
             int v=vt[u][i].v, cost=vt[u][i].cost;
             if(dis[v]>dis[u]+cost)
             {
                 dis[v]=dis[u]+cost;  ///松弛操作
                 if(!inque[v])   ///防止节点重复进队列
                 {
                     inque[v]=1;
                     que[t++]=v;
                     if(t==maxn) t=0;  ///循环队列
                 }
             }
         }
     }
     for(int i=1; i<=n; i++)
     {
         if(dis[i]<=600)
         {
             g[mp[start]][mp[i]]=1;
         }
     }
 }
 
 void floyd()
 {
     for(int k=0; k<=num+1; k++)
         for(int i=0; i<=num+1; i++)
            for(int j=0; j<=num+1; j++)
            {
                if(g[i][j]>g[i][k]+g[k][j])
                     g[i][j]=g[i][k]+g[k][j];
            }
 }
 
 int main()
 {
     int h, m, u, v, cost;
     while(cin >> n, n)
     {
         cin >> num;
         mp.clear();
         for(int i=0; i<=n; i++)
             vt[i].clear();
         for(int i=0; i<=num+2; i++)
             for(int j=0; j<=num+2; j++)
             {
                 g[i][j]=INF;
                 if(i==j) g[i][j]=0;
             }
         for(int i=1; i<=num; i++)
         {
             scanf("%d",st+i);
             mp[st[i]]=i;
         }
         st[0]=1;
         mp[1]=0;
         st[num+1]=n;
         mp[n]=num+1;
         cin >> m;
         for(int i=0; i<m; i++)
         {
             scanf("%d%d%d",&u,&v,&cost);
             vt[u].push_back(Node(v,cost));
             vt[v].push_back(Node(u,cost));
         }
         for(int i=0; i<=num; i++)
             spfa(st[i]);
         floyd();
         if(g[0][num+1]==INF)
             cout << -1 <<endl;
         else
             cout << g[0][num+1]-1 <<endl;
     }
     return 0;
 }

 

 

 

解题参考:http://www.cnblogs.com/kane0526/archive/2012/12/14/2818747.html


  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。