2 条题解
-
1Admity LV 4 @ 2017-10-30 16:10:24
这道题我是拿状压做的,虽然慢了点(#滑稽)
因为m<=20,且1,m,不受限制所以可以说m<=18这样状压就妥妥的了。我们完全可以先预处理出来在那些点能用的情况下1~m的最短路,然后将所有可行解建一个链表,缩短时间,然后再算出来每一天那些码头不能用,然后传统DP就好了。#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<string> #include<cmath> using namespace std; int t,n,m,k,zz,d; struct ro{ int to,l; int next; }road[1000]; int a[40]; void build(int x,int y,int z){ zz++; road[zz].to=y; road[zz].next=a[x]; road[zz].l=z; a[x]=zz; } int dis[(1<<18)+5][21]; int q[200],zt[105],head,en; bool rd[200]; bool yx; int pre[(1<<18)+5]; bool spfa(int tt){ memset(q,0,sizeof(q)); head=1,en=0; dis[tt][1]=0; rd[1]=1; en++; q[en]=1; while(en>=head) { int x=q[head]; head++; rd[x]=0; for(int i=a[x];i>0;i=road[i].next) { int y=road[i].to; if(y==n||(1<<(y-2)&tt)) { if(dis[tt][y]>dis[tt][x]+road[i].l) { dis[tt][y]=dis[tt][x]+road[i].l; if(!rd[y]) { rd[y]=1; en++; q[en]=y; } } } } } if(dis[tt][n]!=dis[tt][0]) return 1; return 0; } int f[2][(1<<18)+5]; int main(){ memset(pre,-1,sizeof(pre)); memset(dis,0x3f,sizeof(dis)); scanf("%d%d%d%d",&t,&n,&k,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); build(x,y,z); build(y,x,z); } int lla=0;; for(int i=0;i<(1<<(n-2));i++) { if(spfa(i)) { if(i==0) yx=1; pre[lla]=i; lla=i; } } scanf("%d",&d); for(int i=1;i<=d;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); for(int j=y;j<=z;j++) zt[j]|=(1<<(x-2)); } int la=1,now=0,mn=-k; for(int i=1;i<=t;i++) { swap(la,now); int mn2=0x7fffffff; for(int j=0;j!=-1;j=pre[j]) { if((j&zt[i])||((!yx)&&j==0)) continue; if(f[la][j]) { f[now][j]=min(f[la][j]+dis[j][n],mn+k+dis[j][n]); mn2=min(mn2,f[now][j]); } else { f[now][j]=mn+k+dis[j][n]; mn2=min(mn2,f[now][j]); } } memset(f[la],0,sizeof(f[la])); mn=mn2; } printf("%d\n",mn); //while(1); return 0; }
-
02018-01-21 10:32:04@
WA*n
于是拿vijos试水保ac率
应该在填表的时候先初始化f[i]=t[1][i] 就不用在最后-K了
先用最短路预处理 然后dp
t[i][j]表示i~j天只走一条最短路的花销
f[i]表示到第i天的最少花销
边界f[0]=0 f[i]=t[1][i]
然后f[i]=min(f[i],f[j]+t[j+1][i]+K) K为换路的费用 0<=j#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; int n, m, K, E,d; struct edge { int v, nxt,w; }e[801]; //n*n*2 无向图 int p[21], eid=0; long long dist[21], t[101][101],f[101]; //t表示i~j天都走同一路线的最短路 inline void ins(int u,int v,int w) { eid++; e[eid].v = v; e[eid].w = w; e[eid].nxt = p[u]; p[u] = eid; } inline void ins2(int u, int v, int w) { ins(u, v, w); ins(v, u, w); } inline int read() { int x; scanf("%d", &x); return x; } bool ava[21],book[101][21]; void spfa() { bool inq[21]; queue<int> q; //memset(ava, true, sizeof(ava)); memset(dist, 0x3f, sizeof(dist)); memset(inq, false, sizeof(inq)); q.push(1); inq[1] = true; dist[1] = 0; while (!q.empty()) { //预处理每个时刻的最短路 int u = q.front(); q.pop(); int v; inq[u] = false; for (int i = p[u]; i; i = e[i].nxt) { v = e[i].v; if(ava[v]) if (dist[u] + e[i].w < dist[v]) { dist[v] = dist[u] + e[i].w; if (!inq[v]) { inq[v] = 1; q.push(v); } } } } } void solve() { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { memset(ava, true, sizeof(ava)); for(int k=1;k<=m;k++) for(int l=i;l<=j;l++) if(!book[l][k]) //第l天k不能用 { ava[k] = false; break; } spfa(); dist[m] >= 0x3f ? t[i][j] = dist[m] : t[i][j] = dist[m] * (j - i + 1); } memset(f, 0x3f, sizeof(f)); f[0] = 0; for (int i = 1; i <= n; i++) //处理每一天 { f[i] = t[1][i]; for (int j = 0; j < i; j++) { //前j-1天的最小花销+j~i天的最短路之和+K(换路花销) f[i] = min(f[i], f[j] + t[j + 1][i] + K); } } } int main() { scanf("%d%d%d%d", &n, &m, &K, &E); memset(book, true, sizeof(book)); for (int i = 1; i <= E; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); ins2(x, y, z); } scanf("%d", &d); for (int i = 0; i < d; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); for (int j = y; j <= z; j++) book[j][x] = false; //标记是否可用 } solve(); cout <<f[n]; //system("pause"); return 0; }
- 1
信息
- 难度
- 4
- 分类
- (无)
- 标签
- 递交数
- 134
- 已通过
- 52
- 通过率
- 39%
- 被复制
- 1
- 上传者