音乐制作网站,网站建设优化服务新闻,哈尔滨城乡建设局网站首页,网站制作价目表最短路/DP 这题数据规模并不大#xff01;#xff01;这是重点……… 所以直接暴力DP就好了#xff1a;f[i]表示前 i 天的最小花费#xff0c;则有$f[i]min\{f[j]cost[j1][i]k\} (0\leq j \leq i-1)$其中cost数组表示第L天到第R天只用一种运输方案连续运$R-L1$天的最小代价…最短路/DP 这题数据规模并不大这是重点……… 所以直接暴力DP就好了f[i]表示前 i 天的最小花费则有$f[i]min\{f[j]cost[j1][i]k\} (0\leq j \leq i-1)$其中cost数组表示第L天到第R天只用一种运输方案连续运$R-L1$天的最小代价因为n很小所以暴力枚举L、R用最短路算法来算…… 记得开long long 1 /**************************************************************2 Problem: 10033 User: Tunix4 Language: C5 Result: Accepted6 Time:52 ms7 Memory:1396 kb8 ****************************************************************/9
10 //BZOJ 1003
11 #includevector
12 #includecstdio
13 #includecstring
14 #includecstdlib
15 #includeiostream
16 #includealgorithm
17 #define rep(i,n) for(int i0;in;i)
18 #define F(i,j,n) for(int ij;in;i)
19 #define D(i,j,n) for(int ij;in;--i)
20 #define pb push_back
21 using namespace std;
22 inline int getint(){
23 int v0,sign1; char chgetchar();
24 while(ch0||ch9){ if (ch-) sign-1; chgetchar();}
25 while(ch0ch9){ vv*10ch-0; chgetchar();}
26 return v*sign;
27 }
28 const int N110,M1000,INF100000000;
29 typedef long long LL;
30 /******************tamplate*********************/
31 int to[M],next[M],head[N],len[M],cnt;
32 void ins(int x,int y,int z){
33 to[cnt]y; next[cnt]head[x]; head[x]cnt; len[cnt]z;
34 }
35 void add(int x,int y,int z){
36 ins(x,y,z);ins(y,x,z);
37 }
38 /*******************edge************************/
39 int n,m,k,e;
40 LL f[N],cost[N][N],d[N];
41 int Q[M];
42 bool can[N][N],vis[N],inq[N];
43 LL spfa(){
44 int l0,r-1;
45 F(i,2,m) d[i]INF;
46 d[1]0;inq[1]1;
47 Q[r]1;
48 while(lr){
49 int xQ[l];
50 inq[x]0;
51 for(int ihead[x];i;inext[i])
52 if(vis[to[i]] d[to[i]]d[x]len[i]){
53 d[to[i]]d[x]len[i];
54 if(!inq[to[i]]){
55 Q[r]to[i];
56 inq[to[i]]1;
57 }
58 }
59 }
60 return d[m];
61 }
62
63 int main(){
64 #ifndef ONLINE_JUDGE
65 freopen(1003.in,r,stdin);
66 freopen(1003.out,w,stdout);
67 #endif
68 ngetint(); mgetint(); kgetint(); egetint();
69 int x,y,z;
70 F(i,1,e){
71 xgetint(); ygetint(); zgetint();
72 add(x,y,z);
73 }
74 int qgetint();
75 F(i,1,m) F(j,1,n) can[i][j]1;
76 F(i,1,q){
77 xgetint(); ygetint(); zgetint();
78 F(j,y,z) can[x][j]0;
79 }
80 F(i,1,n) F(j,i,n){
81 F(x,1,m) vis[x]1;
82 F(x,2,m-1) F(k,i,j) if(!can[x][k]) vis[x]0;
83 cost[i][j]spfa()*(j-i1);
84 }
85 F(i,1,n) f[i]cost[1][i];
86 F(i,1,n) F(j,0,i-1) f[i]min(f[i],f[j]cost[j1][i]k);
87 printf(%lld\n,f[n]);
88 return 0;
89 }
90 View Code 1003: [ZJOI2006]物流运输trans Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3956 Solved: 1638[Submit][Status][Discuss] Description 物 流公司要把一批货物从码头A运到码头B。由于货物量比较大需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路 线以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在有的时候某个码头会无法装卸货物。这时候就必须修改运输路线让货物能够按时到达目的 地。但是修改路线是一件十分麻烦的事情会带来额外的成本。因此物流公司希望能够订一个n天的运输计划使得总成本尽可能地小。 Input 第 一行是四个整数n1n100、m1m20、K和e。n表示货物运输所需天数m表示码头总数K表示每 次修改运输路线所需成本。接下来e行每行是一条航线描述包括了三个整数依次表示航线连接的两个码头编号以及航线长度0。其中码头A编号为 1码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来一行是一个整数d后面的d行每行是三个整数P 1 P m、a、b1 a b n。表示编号为P的码头从第a天到第b天无法装卸货物含头尾。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头A到码头B的 运输路线。 Output 包括了一个整数表示最小的总成本。总成本n天运输路线长度之和K*改变运输路线的次数。 Sample Input 5 5 10 8 1 2 1 1 3 3 1 4 2 2 3 2 2 4 4 3 4 1 3 5 2 4 5 2 4 2 2 3 3 1 1 3 3 3 4 4 5 Sample Output 32 HINT 前三天走1-4-5后两天走1-3-5这样总成本为(22)*3(32)*21032 Source [Submit][Status][Discuss] 转载于:https://www.cnblogs.com/Tunix/p/4403396.html
