关键词：
题目描述
特工玛利亚被送到S市执行一个特别危险的任务。她需要利用地铁完成他的任务，S市的地铁只有一条线路运行，所以并不复杂。
玛利亚有一个任务，现在的时间为0，她要从第一个站出发，并在最后一站的间谍碰头。玛利亚知道有一个强大的组织正在追踪她，她知道如果一直呆在一个车站，她会有很大的被抓的风险，躲在运行的列车中是比较安全的。所以，她决定尽可能地呆在运行的列车中，她只能往前或往后坐车。
玛利亚为了能准时且安全的到达最后一个车站与对方碰头，需要知道在在车站最小等待时间总和的计划。你必须写一个程序，得到玛丽亚最短的等待时间。当然，到了终点站之后如果时间还没有到规定的时刻，她可以在车站里等着对方，只不过这个等待的时刻也是要算进去的。
这个城市有n个车站，编号是1-n，火车是这么移动的：从第一个车站开到最后一个车站。或者从最后一站发车然后开会来。火车在每特定两站之间行驶的时间是固定的，我们也可以忽略停车的时间，玛利亚的速度极快，所以他可以迅速上下车即使两辆车同时到站。
输入输出格式
输入格式：
输入文件包含多组数据，每组数据都由7行组成
第1行：一个正整数N（2<=N<=50）表示站的数量
第2行：一个正整数T（0<=T<=200）表示需要的碰头时间
第3行：1-（n-1）个正整数（0<ti<70）表示两站之间列车的通过时间
第4行：一个整数M1（1<=M1<=50）表示离开第一个车站的火车的数量
第5行：M1个正整数：d1，d2……dn，（0<=d<=250且di<di+1）表示每一列火车离开第一站的时间
第6行：一个正整数M2（1<=M2<=50）表示离开第N站的火车的数量
第7行：M2个正整数：e1,e2……eM2,(0<=e<=250且ei<ei+1)表示每一列火车离开第N站的时间
最后一行有一个整数0。
输出格式：
对于每个测试案例，打印一行“Case Number N: ”（N从1开始）和一个整数表示总等待的最短时间或者一个单词“impossible”如果玛丽亚不可能做到。按照样例的输出格式。
输入输出样例
4 55 5 10 15 4 0 5 10 20 4 0 5 10 15 4 18 1 2 3 5 0 3 6 10 12 6 0 3 5 7 12 15 2 30 20 1 20 7 1 3 5 7 11 13 17 0
Case Number 1: 5 Case Number 2: 0 Case Number 3: impossible
/* 思路是好想，设f[i][j]为前i分钟走到j站的最少等待时间，a[i][j][0/1]代表第i分钟有无从前或从后来的车， 自己写的转移方程感觉很有道理，交上去一个点也过不了，然后看看题解，和自己的差不多，可能有些细节没处理好吧。 */ #include<cstdio> #include<algorithm> #include<cstring> #define M 1005 #define inf 0x3f3f3f3f using namespace std; int n,T,m,w[M],f[M][M],a[M][M][2]; void init() { int i,j,start; memset(f,0x3f3f3f3f,sizeof(f)); memset(a,0,sizeof(a)); scanf("%d",&T); for(i=1;i<n;i++) scanf("%d",&w[i]); scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d",&start); a[start][1][0]=1; for(j=2;j<=n;j++) { start+=w[j-1]; a[start][j][0]=1; } } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d",&start); a[start][n][1]=1; for(j=n-1;j>=1;j--) { start+=w[j]; a[start][j][1]=1; } } return; } void work() { int i,j; f[0][1]=0; for(i=1;i<=T;i++) { for(j=1;j<=n;j++) { f[i][j]=f[i-1][j]+1; if(j>=2&&i-w[j-1]>=0&&a[i-w[j-1]][j-1][0]) f[i][j]=min(f[i][j],f[i-w[j-1]][j-1]); if(j<n&&i-w[j]>=0&&a[i-w[j]][j+1][1]) f[i][j]=min(f[i][j],f[i-w[j]][j+1]); } } return ; } int main() { int kase=0; while(scanf("%d",&n)==1&&n!=0) { init(); work(); printf("Case Number %d: ",++kase); if(f[T][n]<inf) printf("%d\n",f[T][n]); else printf("impossible\n"); } return 0; }
洛谷——p1262间谍网络
P1262间谍网络题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部... 查看详情
洛谷p1262间谍网络
题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以... 查看详情
洛谷p1262间谍网络
...bsp; P1262间谍网络 题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则 查看详情
洛谷p1262间谍网络==codevs4093ez的间谍网络
4093EZ的间谍网络时间限制:10s 空间限制:128000KB 题目等级:黄金Gold题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受... 查看详情
洛谷1262间谍网络
tarjan缩点后找入度为零的强连通分量，加上它的sum即可但注意到还有NO的可能，所以大致有两种方法：1.tarjan之前先来一遍bfs2.tarjan内加一个数组维护最小编号貌似前者比较好写qwq1#include<cstdio>2#include<cstring>3usingnamespacestd;... 查看详情
tarjan缩点以及链式前向星的基本+应用（洛谷1262间谍网络）
题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以... 查看详情
洛谷p1710地铁涨价
...，市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有N个地铁站，同时有M小段地铁连接两个不同的站。地铁计价方式很简单。从A站到B站，每经过一小段铁路（连接直接相邻的两个点的一... 查看详情
洛谷——p1910l国的战斗之间谍
...好：“知己知彼，百战不殆”。L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。你现在有N个人选，每个人都有这样一些数据：A（能得到多少资料）、B（伪装能力有多差）、C（要多少工资）。已知敌人... 查看详情
洛谷p1262间谍网络label:kosarajn说:我就是不用tarjan&&tarjan待做
题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以... 查看详情
强连通分量——间谍网络(洛谷_1262)——tarjan求scc
scc缩点建图处理#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<stack>usingnamespacestd;inlineintread(){intt=1,num=0;charc=g 查看详情
洛谷p1910l国的战斗之间谍（水题日常）
...好：“知己知彼，百战不殆”。L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。你现在有N个人选，每个人都有这样一些数据：A（能得到多少资料）、B（伪装能力有多差）、C（要多少工资）。已知敌人... 查看详情
uva1025，城市的间谍
...目链接：https://uva.onlinejudge.org/external/10/1025.pdf 题意：地铁是线性的，有n个站，编号（1~n）,M1辆从左至右的车，和M2辆从右至左的车，发车时刻给出，然后是，每两个站之间要跑多长时间。一个间谍要从1车站到n车站，但是他... 查看详情
洛谷p1071潜伏者
...1071潜伏者题目描述R国和S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于S国的R国间谍小C终于摸清了S国军用密码的编码规则：1．S国军方内部欲发送的原信息经过加密后在网络上发送，原信... 查看详情
洛谷p1071潜伏者题解
...show?pid=1071题目描述R国和S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于S国的R国间谍小C终于摸清了S国军用密码的编码规则：1．S国军方内部欲发送的原信息经过加密后在网络上发送，原信... 查看详情
ac日记——潜伏者洛谷p1071（模拟）
题目描述R国和S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于S国的R国间谍小C终于摸清了S国军用密码的编码规则：1．S国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容... 查看详情
[noip2009]提高组洛谷p1071潜伏者
题目描述R国和S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于S国的R国间谍小C终于摸清了S国军用密码的编码规则：1．S国军方内部欲发送的原信息经过加密后在网络上发送，原信息的... 查看详情
uva1025城市里的间谍(代码片段)
某城市地铁是线性的,有n（2≤n≤50）个车站,从左到右编号1~n。有M1辆列车从第1站开始往右开,还有M2辆列车从第n站开始往左开。 列车在相邻站台间所需的运行时间是固定的，因为所有列车的运行速度是相同的。 ... 查看详情
动态规划初步--城市里的间谍(代码片段)
一、题目某城市的地铁是线性的，有n(2≤n ≤50)个车站，从左到右编号为1~n。有M1辆车从第一站开始往右开，还有M2辆从第n站开始往左开。在时刻0，Mario从第一站出发，目的是在T时刻会见在n站的一个间谍。要求其在车站的等... 查看详情