• 周四. 2月 29th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[ZJOI2006]物流运输trans

admin

11月 28, 2021
pre.cjk { font-family: “Droid Sans Fallback”, monospace }
p { margin-bottom: 0.25cm; line-height: 120% }
a:link { }

先枚举任意两天,SPFA求出这两天之间的公共最短路,记为cost[i][j],这个可以把这两天之间的所有不能走到的点标记一下,然后求最短路.
求出了这个东西,就发现这个长得很像DP.f[i]表示到i这天的最小费用.
f[i]=max(f[i],f[j]+cost[j+1][i]+k),f[i]初值为cost[1][i].

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<string>
 8 #include<vector>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 #define maxn 22
15 #define inf 1999999999
16 using namespace std;
17 struct data{
18   int nex,to,w;
19 }e[maxn*maxn*2];
20 int head[maxn],edge=0,cost[110][110],bj[22][110],bj1[maxn],n,dis[maxn],f[110];
21 bool vis[maxn];
22 void add(int from,int to,int w){
23   e[++edge].nex=head[from];
24   e[edge].to=to;
25   e[edge].w=w;
26   head[from]=edge;
27 }
28 queue<int>q;
29 void SPFA(int s,int t){
30   for(int i=1;i<=20;i++) dis[i]=inf,bj1[i]=0;
31   for(int i=s;i<=t;i++)
32     for(int j=1;j<=n;j++)
33       if(bj[j][i]) bj1[j]=1;
34   q.push(1);dis[1]=0;
35   while(!q.empty()){
36     int u=q.front();
37     q.pop();
38     vis[u]=0;
39     for(int i=head[u];i;i=e[i].nex){
40       int v=e[i].to;
41       if(bj1[v]) continue;
42       if(dis[v]>dis[u]+e[i].w){
43     dis[v]=dis[u]+e[i].w;
44     if(!vis[v]) q.push(v),vis[v]=1;
45       }
46     }
47   }
48   if(dis[n]!=inf)
49     cost[s][t]=dis[n]*(t-s+1);
50   else cost[s][t]=inf;
51 }
52 int main()
53 {
54   freopen("!.in","r",stdin);
55   freopen("!.out","w",stdout);
56   int day,k,m,x,y,z;
57   scanf("%d%d%d%d",&day,&n,&k,&m);
58   for(int i=1;i<=m;i++)
59     scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
60   int d;scanf("%d",&d);
61   for(int i=1;i<=d;i++){
62     scanf("%d%d%d",&x,&y,&z);
63     for(int i=y;i<=z;i++)
64       bj[x][i]=1;
65   }
66   for(int i=1;i<=day;i++)
67     for(int j=i;j<=day;j++)
68       SPFA(i,j);//,printf("%d %d %d
",i,j,cost[i][j]);
69   for(int i=1;i<=day;i++) f[i]=inf;
70   for(int i=1;i<=day;i++){
71     f[i]=cost[1][i];
72     for(int j=0;j<i;j++)
73       if(cost[j+1][i]<inf)
74       f[i]=min(f[i],f[j]+cost[j+1][i]+k);
75   }
76   printf("%d",f[day]);
77   return 0;
78 }

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注