首页 > ACM题库 > HDU-杭电 > HDU 4522-湫湫系列故事――过年回家-Dijkstra-[解题报告]HOJ
2015
07-17

HDU 4522-湫湫系列故事――过年回家-Dijkstra-[解题报告]HOJ

湫湫系列故事――过年回家

问题描述 :

  出门在外,最想念的还是家,对在深圳腾讯工作的HR湫湫来说,春节回家是一年中最期盼的事,不仅可以见到阔别已久的亲人,还能以相亲的名义调侃众多帅哥(她的内心告诉她:如果相亲能遇到参加过腾讯编程马拉松的同学,就直接把自己嫁了~)。
  同时,每年的春节湫秋也都会纠结一把,因为车票实在是太难抢了,不过2013的春节有点特殊,作为一个曾经的ACMer,湫湫制作出了很完美的刷票机,也就是说她再也不用担心买不上票了,但是想来想去还是觉得随便买票实在是浪费了辛辛苦苦搞出来的刷票机,所以她决定要用最舒适的方式回家。
  假设湫湫有可能经过的n个城市分别编号从1到n,湫湫要从城市A回到城市B,购票网站上列出了t辆列车行程,每辆车的行程用一个字符串表示,途径的城市间用+号相连,如1+2+3+5代表一辆从1城市分别经过2,3到达5的火车,湫湫可以从中间任意一站出发和下车(路径是单向的,即必须沿字符串从左到右来走),每个字符串对应着一个整数k,k=0表示该车只有硬座,k=1表示该车有卧铺也有硬座,在整个回家的计划中,同一辆车可以坐无限次,为了中途换车的方便,如果在起点坐的是卧铺,则后面乘坐的车必须全是卧铺,同样的,如果在起点坐的是硬座,则后面乘坐的车必须全是硬座,假设一段(一辆车行程中,两相邻城市间为一段)硬座的不舒适度是D1,一段卧铺的不舒适度是D2,求湫湫回家最小的不舒适度。

输入:

  输入数据的第一行包含一个整数Q,表示测试数据的组数;
  每组数据的第一行是2个正整数n和t,分别表示城市数和列车数;
  接下来t行,每行一个字符串表示列车行程,字符串长度小于10000,每个字符串后跟一个整数k(k为0或1),之间用空格隔开;
  接下来一行是D1,D2,其含义见题目描述;
  最后一行是2个正整数A和B,表示起始和终点城市。

  [Technical Specification]
  1 <= Q <= 100
  1 < n <= 200
  1 < t <= 1000
  0 < D1 <= 10000, 0 < D2 <= 10000,D1和D2的大小关系不确定
  1 <= A, B <= n 且 A <> B

输出:

  输入数据的第一行包含一个整数Q,表示测试数据的组数;
  每组数据的第一行是2个正整数n和t,分别表示城市数和列车数;
  接下来t行,每行一个字符串表示列车行程,字符串长度小于10000,每个字符串后跟一个整数k(k为0或1),之间用空格隔开;
  接下来一行是D1,D2,其含义见题目描述;
  最后一行是2个正整数A和B,表示起始和终点城市。

  [Technical Specification]
  1 <= Q <= 100
  1 < n <= 200
  1 < t <= 1000
  0 < D1 <= 10000, 0 < D2 <= 10000,D1和D2的大小关系不确定
  1 <= A, B <= n 且 A <> B

样例输入:

1
6 5
2+4+3+5+1+6 1
5+4+2+3+1 1
3+2+5+1+6 1
6+2 0
6+3+1+4+5+2 0
3 2
5 3

样例输出:

4

若菜只会3题,orz,继续刷题吧。。。

hdu 4520:

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

思路:就是一个去掉最高分和最低分求平均分,在和原来的分数比较,看哪个裁判最接近。

 #include<iostream>
 #include<cmath>
 using namespace std;
 
 int main(){
     int n;
     double num[40];
     while(~scanf("%d",&n)&&n){
         double max=-1;
         double min=400;
         double sum=0;
         for(int i=0;i<n;i++){
             scanf("%lf",&num[i]);
             if(num[i]<min)min=num[i];
             if(num[i]>max)max=num[i];
             sum+=num[i];
         }
         sum=(sum-min-max)/(n-2);
         int pos=0;
         min=400;
         for(int i=0;i<n;i++){
             if(fabs(sum-num[i])<min){
                 min=fabs(sum-num[i]);
                 pos=i+1;
             }
         }
         printf("%d\n",pos);
     }
     return 0;
 }

hdu 4522:

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

思路:就是求最短路,建两个图,一个是硬座的,一个是卧铺的,然后两次Dijkstra(orz,若菜只会这么干),如果不存在路径,就输出-1,否则,再比较花费。

 #include<iostream>
 #include<cstring>
 const int N=207;
 const int inf=1e7;
 using namespace std;
 int dist1[N];
 int dist0[N];
 int visited[N];
 int edge1[N][N];
 int edge0[N][N];
 int n,m,k;
 
 void Dijkstra1(int u){
     memset(visited,0,sizeof(visited));
     for(int i=1;i<=n;i++){
         dist1[i]=edge1[u][i];
     }
     visited[u]=1;
     for(int i=1;i<n;i++){
         int min=inf,v=u;
         for(int j=1;j<=n;j++){
             if(dist1[j]<min&&!visited[j]){
                 min=dist1[j];
                 v=j;
             }
         }
         if(min==inf)return ;
         visited[v]=1;
         for(int k=1;k<=n;k++){
             if(!visited[k]&&edge1[v][k]<inf&&dist1[v]+edge1[v][k]<dist1[k]){
                 dist1[k]=dist1[v]+edge1[v][k];
             }
         }
     }
 }
 
 void Dijkstra0(int u){
     memset(visited,0,sizeof(visited));
     for(int i=1;i<=n;i++){
         dist0[i]=edge0[u][i];
     }
     visited[u]=1;
     for(int i=1;i<n;i++){
         int min=inf,v=u;
         for(int j=1;j<=n;j++){
             if(dist0[j]<min&&!visited[j]){
                 min=dist0[j];
                 v=j;
             }
         }
         if(min==inf)return ;
         visited[v]=1;
         for(int k=1;k<=n;k++){
             if(!visited[k]&&edge0[v][k]<inf&&dist0[v]+edge0[v][k]<dist0[k]){
                 dist0[k]=dist0[v]+edge0[v][k];
             }
         }
     }
 }
 
 
 
 int main(){
     int _case;
     scanf("%d",&_case);
     while(_case--){
         scanf("%d%d",&n,&m);
         char str[10100];
         for(int i=1;i<=n;i++){
             for(int j=1;j<=n;j++){
                 edge1[i][j]=edge1[j][i]=inf;
                 edge0[i][j]=edge0[j][i]=inf;
             }
         }
         for(int i=1;i<=m;i++){
             scanf("%s%d",str,&k);
             int len=strlen(str);
             int s1=0,s2=0;
             if(k==1){
                 for(int j=0;j<len;j++){
                     //这边一开始没注意到,re了好多次,orz
                     while(str[j]!='+'&&j<len){
                         s2=s2*10+str[j]-'0';
                         j++;
                     }
                     edge1[s1][s2]=1;//卧铺的
                     edge0[s1][s2]=1;//硬座的
                     s1=s2;
                     s2=0;
                 }
             }else if(k==0){
                 for(int j=0;j<len;j++){
                     while(str[j]!='+'&&j<len){
                         s2=s2*10+str[j]-'0';
                         j++;
                     }
                     edge0[s1][s2]=1;//硬座的
                     s1=s2;
                     s2=0;
                 }
             }
         }
         int d1,d2,u,v;
         scanf("%d%d%d%d",&d1,&d2,&u,&v);
         Dijkstra1(u);//开始是卧铺
         Dijkstra0(u);//开始是硬座
         if(dist1[v]==inf&&dist0[v]==inf){
             printf("-1\n");
         }else if(dist1[v]==inf&&dist0[v]<inf){
             printf("%d\n",dist0[v]*d1);
         }else if(dist1[v]<inf&&dist0[v]==inf){
             printf("%d\n",dist1[v]*d2);
         }else {
             printf("%d\n",min(dist1[v]*d2,dist0[v]*d1));
         }
     }
     return 0;
 }

hdu 4524:

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

思路:就是最后所有的数都必须为0才能逃离迷宫,直接暴力之。

 #include<iostream>
 using namespace std;
 int num[1000007];
 
 int main(){
     int _case;
     scanf("%d",&_case);
     while(_case--){
         int n;
         scanf("%d",&n);
         for(int i=1;i<=n;i++){
             scanf("%d",&num[i]);
             if(num[i]>=num[i-1]){
                 num[i]-=num[i-1];
                 num[i-1]=0;
             }
         }
         int flag=0;
         for(int i=1;i<=n;i++){
             if(num[i]){
                 flag=1;
                 break;
             }
         }
         if(flag){
             printf("I will never go out T_T\n");
         }else 
             printf("yeah~ I escaped ^_^\n");
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/wally/archive/2013/03/25/2980601.html