- 时间限制:10000ms 内存限制:100000kB
- 描述
- 德鲁伊带着他的精灵熊在前线作战……
德鲁伊打到了钱，会让他的熊宝宝回家买东西
德鲁伊在1号点，家在M号点，中间有e条无向边，通过每一条边都有一个时间，德鲁伊会让他的熊宝宝买N次东西，熊宝宝会选一条路来回家，但是这些点有限制，每一个点在一定的次数内不能通过，所以，熊宝宝有时候会更换路径。
德鲁伊可以让他的熊宝宝瞬间到他身边，所以熊宝宝买完东西回来不需要时间。
熊宝宝的路径是德鲁伊想的，所以每次熊宝宝更换路径都要耗费K的时间（第一次想的路径不花时间）
现在，德鲁伊想知道，买N次东西最少所需要的总时间是多少？- 输入
- 第一行，四个数N，M，K，e
接下来e行，每行三个数s，t，len，表示s到t有一条无向边，通过时间为len
下面一行有一个数T，表示有T条限制
接下来T行，每行三个数x，l，r，表示在l次到r次不能通过x- 输出
- 一个数，表示最短总时间
- 样例输入
- 样例输出
- 提示
- N<=10000,M<=10,K<=5000
T<=100
【Solution ① Of Loogint】
本题是浙江省选的一道水题的变形，这道题是一道较简单的动态规划。
F[i]表示到第i次所需要的最少时间
F[i]←min{F[j]+SPFA(j+1,i)*(i-j)+k}(0<=j<=i-1)
最后结果是F[n]-k
方程中的SPFA表示的是从j+1天到i天不改变方案所能取得的最短路径长度，这个只要对SPFA中的vis数组进行一定的预处理即可。
但魂之挽歌那个魂淡把n从100加强到了10000，O(n^2)的程序就跑得很吃力了…
【Code 1: Tle】
1: Program Dryad(input,output);2: type point=^node;3: node=record4: data,weight:longint;5: next:point;6: end;7: var que:array[1..2000]of longint;8: vis,forbid:array[1..20]of boolean;9: dist:array[1..20]of longint;10: limit:array[1..100,0..100]of longint;11: map:array[1..20]of point;12: F:array[0..100]of longint;13: i,j,n,m,k,e,x,y,len,t,w,l,r:longint;14: p:point;15: Function SPFA(l,r:longint):longint;16: var i,j,head,tail,quehead:Longint;edge:point;17: begin18: fillchar(que,sizeof(que),0);19: fillchar(vis,sizeof(vis),false);20: for i:=1 to m do dist[i]:=19940805;21: fillchar(forbid,sizeof(forbid),false);22: for i:=l to r do23: for j:=1 to limit[i,0] do24: forbid[limit[i,j]]:=true;25: dist[1]:=0;vis[1]:=true;26: head:=0;tail:=1;27: que[tail]:=1;28: while head<tail do29: begin30: inc(head);31: quehead:=que[head];32: vis[quehead]:=false;33: edge:=map[quehead];34: while edge<>nil do35: begin36: if not forbid[edge^.data] then37: if dist[quehead]+edge^.weight<dist[edge^.data] then38: begin39: dist[edge^.data]:=dist[quehead]+edge^.weight;40: if not(vis[edge^.data]) then41: begin42: inc(tail);43: que[tail]:=edge^.data;44: vis[edge^.data]:=true;45: end;46: end;47: edge:=edge^.next;48: end;49: end;50: exit(dist[m]);51: end;52: begin53: readln(n,m,k,e);54: for i:=1 to e do55: begin56: readln(x,y,len);57: new(p);p^.data:=y;p^.weight:=len;p^.next:=map[x];map[x]:=p;58: new(p);p^.data:=x;p^.weight:=len;p^.next:=map[y];map[y]:=p;59: end;60: readln(t);61: for i:=1 to t do62: begin63: readln(x,l,r);64: for j:=l to r do65: begin66: inc(limit[j,0]);67: limit[j,limit[j,0]]:=x;68: end;69: end;70: for i:=1 to n do71: begin72: F[i]:=maxlongint;73: for j:=0 to i-1 do74: begin75: w:=SPFA(j+1,i);76: if w=19940805 then continue;77: if F[i]>F[j]+w*(i-j)+k then78: F[i]:=F[j]+w*(i-j)+k;79: end;80: end;81: writeln(F[n]-k);82: end.
{
This Code is Accepted at ZJOI2006_Trans.
http://www.zybbs.org/JudgeOnline/problem.php?id=1003
/**************************************************************
Problem: 1003
User: Loongint
Language: Pascal
Result: Accepted
Time:68 ms
Memory:304 kb
****************************************************************/
}
【Solution ② of Loongint】
注意到原题的数据范围：天数是100，而节点数是20。Dyrad这个题的数据：次数10000，节点只有10。
所以我们变换一下动归的方式。
先DFS处理出所有的路径，然后把每一条路径看成一个体积1，价值为其路径长度和的物品，那么就成为了一个背包问题，总体积为次数n。
F[i,j]表示到第i次且前一次所选择的路径为j所能获得的最短路程。
F[i,j]←min{F[i-1,j]+value[j],F[i-1,l]+value[l]+k}//j and l is legal in this time.
结果从F[n,i](1=<i<=MaxNumOfPath)中找即可。
效率是O(n*MaxNumPath)的。
代码不给了…因为Dsqwwe说，这样也超时，路径条数太多。
【Solution ③ of Loongint】
暴打魂之挽歌一顿…..（那家伙的代码ms是O(n)的….，马萨卡是贪心？）