hdu----(4522)湫湫系列故事——过年回家(最短路)

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

Time Limit: 500/200 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1095    Accepted Submission(s): 226

Problem Description

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

Input

  输入数据的第一行包含一个整数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

Output

  对于每组数据,如果湫湫可以到达目的地,则输出一个整数,表示湫湫到家所需的最小不舒适度。如果不能到达则直接输出-1。

Sample Input

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

Sample Output

4

Source

2013腾讯编程马拉松初赛第四场(3月24日)

最短路:  用狄斯喹诺算法求解:

  对其进行一次硬座求最短和软卧求最短....

代码:

 1 //#define LOCAL
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 using namespace std;
 7 const int inf=0x3f3f3f3f;
 8 const int maxn=250;
 9 int city[maxn][maxn],lowc[maxn];
10 char str[10050];
11 bool vis[maxn];
12 int Q,n,t,k;
13 int d[3];
14 int Distra(int st,int en,int type)
15 {
16   int i,j;
17   memset(vis,'\0',sizeof(vis));
18   memset(lowc,0,sizeof(lowc));
19   vis[st]=1;
20   for(i=1;i<=n;i++){
21      if(city[st][i]>=type)
22         lowc[i]=1;
23      else
24         lowc[i]=inf;
25   }
26    lowc[st]=0;  //原点为0
27    int pre=st,minc;
28   for(i=1;i<n;i++)
29   {
30         minc=inf;
31       for(j=1;j<=n;j++){
32       if(!vis[j]&&city[pre][j]>=type&&1+lowc[pre]<=lowc[j])
33       {
34           lowc[j]=lowc[pre]+1;
35       }
36       }
37       for(j=1; j<=n ;j++)
38     {
39       if(!vis[j]&&lowc[j]<minc)
40       {
41           minc=lowc[j];
42           pre=j;
43       }
44     }
45     vis[pre]=1;
46   }
47   if(lowc[en]==inf)lowc[en]=0;
48   return lowc[en];
49 }
50 int main()
51 {
52    int val,fr,a,b;
53    bool flag;
54    #ifdef LOCAL
55    freopen("test.in","r",stdin);
56    #endif
57    scanf("%d",&Q);
58    while(Q--){
59      scanf("%d%d",&n,&t);
60      memset(city,0,sizeof(city));
61      while(t--){
62          scanf("%s %d",str,&k);
63           fr=val=0;
64           flag=0;
65          for(int i=0; ;i++)
66          {
67               if(str[i]=='\0')str[i]='+',flag=1;
68              if(str[i]!='+')
69            val=val*10+str[i]-'0';
70         else
71         {
72           if(fr==0) fr=val;
73           else
74           {
75             if(city[fr][val]<k+1)
76               city[fr][val]=k+1;
77             fr=val;
78           }
79           val=0;
80         }
81         if(flag) break;
82          }
83      }
84      scanf("%d%d",&d[1],&d[2]);
85          scanf("%d%d",&a,&b);
86      int lenb=Distra(a,b,1);  //以硬座进行查找
87      if(lenb==0)
88              printf("-1\n");
89      else
90      {
91       int lena=Distra(a,b,2);  //以卧铺进行查找
92        if(lena==0)
93            printf("%d\n",lenb*d[1]);
94        else
95           printf("%d\n",min(lena*d[2],lenb*d[1]));
96      }
97    }
98   return 0;
99 }

 一些测试数据:

4
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
6 3
3+4 1
4+2+6 0
3+2+1+6 1
3 2
3 6
6 3
3+4 1
4+2+6 0
3+2+1+6 1
3 2
5 6
6 4
3+4 1
4+2+6 0
3+2+1+6 1
3+1+5+2+6 0
3 2
5 6
*/

分别为: 4 6 -1 6

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小詹同学

Python系列之六——拿什么拯救你?我的大脑

我一定是智障了,话不多说,上图上图~ ? 就是这样10个选择题,你没有看错,我一定是个智障了~佩服不用穷举,也不用参考网上的大...

3654
来自专栏专知

关关的刷题日记79 – Leetcode 9 Palindrome Number

关关的刷题日记79 – Leetcode 9 Palindrome Number 题目 Determine whether an integer is a pa...

3648
来自专栏专知

关关的刷题日记88 – Leetcode 367.Valid Perfect Square

关关的刷题日记88 – Leetcode 367.Valid Perfect Square 题目 Given a positive integer num, w...

3029
来自专栏数据结构与算法

BZOJ1569: [JSOI2008]Blue Mary的职员分配(dp 暴力)

1375
来自专栏专知

【 关关的刷题日记47】Leetcode 38. Count and Say

关关的刷题日记47 – Leetcode 38. Count and Say 题目 The count-and-say sequence is the sequ...

31810
来自专栏数据结构与算法

P1372 又是毕业季I

题目背景 “叮铃铃铃”,随着高考最后一科结考铃声的敲响,三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍,憧憬着未来仍毋忘逝去的歌。1000多个日夜的欢笑...

3234
来自专栏JetpropelledSnake

Python实现简单的三级菜单

话不多说,直奔代码 # 要处理的字典 dic1 = { '北京': { '东城': { ...

6529
来自专栏数据结构与算法

生理周期POJ 1006

Description 人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会...

2757
来自专栏专知

【Leetcode 206】关关的刷题日记70 – Leetcode 206. Reverse Linked List

关关的刷题日记70 – Leetcode 206. Reverse Linked List 题目 Reverse a singly linked list. 题...

3378
来自专栏HansBug's Lab

2729: [HNOI2012]排队

2729: [HNOI2012]排队 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 957  Solved:...

2965

扫码关注云+社区

领取腾讯云代金券