基于DAG模型的最长(短)路问题

漫步云海涧

基于DAG模子的最少(短)路成绩

打点那类成绩三步调：
1.界说无后效性的形态
2.找到每种形态的决议计划状况
3.列出形态转移圆程
标题问题一：城市里的特务(UVA1025）

  某城市天铁是一条曲线，有 n(2≤n≤50）个车站，从左到左编号 1…n。
有M1辆列车从第 1 站开端往左开，另有 M2 辆列车从第 n站开端往左开。列车正在相邻站台间所需的运转工夫是牢固的，由于一切列车的运转速率是不异的。正在时辰 T=0，Mario 从第 1 站动身，目标正在时辰 T（0≤T≤200）会晤车站 n 的一个特务。正在车站等车时简单被抓，以是她决议尽管躲正在开动的水车上，让正在车站等候的工夫尽管短。列车靠站泊车工夫疏忽没有计，且 Mario 技艺活络，立即两辆标的目的差别的列车正在统一工夫靠站，Mario 也能完成换乘。

  输进文件包罗多组数据。
每组数据包罗以下 7 止：
第一止是一个正整数 n，暗示有 n个车站。
第两止是为 T，暗示 Mario 正在时辰 T 会晤车站 n 的特务。
第三止有 n−1 个整数 t1 ,t2 ​,…,t(n−1) ​此中 ti ​ 暗示天铁从车站 i 到 i+1 的止驶工夫。
第四举动 M1 ​ ，及从第一站动身背左开的列车数量。
第五止包罗 M1个正整数a1 ​ ,a2 ​ ,…,a(M1) ​，即每一个列车动身的工夫。
第六举动M 2 ​ ，即从第 n 站动身背左开的列车数量。
第七止包罗 M2 个正整数 b1 ​,b2 ​ ,…,b(M2) ​ ​ ，即每一个列车动身的工夫。
输进文件以一止 0 结尾。
输进样例：
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

阐发标题问题：
工夫是单背流逝的，明显是一个自然的“序”。影响决议计划的只要当前工夫战所处的车站能否有列车开动，以是能够用d(i,j)暗示正在时辰i,您正在车站j(编号为1~n),起码借需求等候几工夫。鸿沟前提必定是此时为时辰T,您曾经正在车站n，以是d[T][n]=0,其他d[T]立即刻T时可是没有正在车站n初初化为无量年夜，那便是dp的鸿沟。
然后便是决议计划方法阐发，没有易发明，统共有三种决议计划，
决议计划1：没有乘坐列车，等一分钟。
决议计划2：乘坐背左开的列车（条件是该时辰下有列车背左收车）
决议计划3：乘坐背左开的列车（条件是该时辰下有列车背左收车）

以下代码中有一个三维数组has，此中has[j][0]暗示正在时辰i,能否有背左的列车从车站j动身；同理has[j][1]暗示正在时辰i，能否有背左的列车从车站j动身，有则为1.数组起首初初化为0.
因而三种决议计划下的形态转移圆程以下：
<strong>1.dp[j]=dp[i+1][j]+1;
2. if(jn&&n){                cin>>T;                memset(has,0,sizeof(has));            for(int i=1;i>t;            t[0]=t[n]=0;            cin>>M1;            for(int i=1;i>x;                    for(int j=1;j>M2;            for(int i=1;i>x;                    for(int j=n;j>=1;j--){                            x+=t[j];                            has[x][j][1]=1;                        }                }            cout<span class="token operator">