[CSP2021]交通规划（traffic）

C++(clang++ 11.0.1) 解法, 执行用时: 1857ms, 内存消耗: 18908K, 提交时间: 2022-08-03 17:47:51
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct Extra
{
	int w,p,c;
	bool operator < (const Extra &b) const
	{
		return p<b.p;
	}
}e[60];
priority_queue<pair<long long,int> > q;
int n,m,T,k,np,tot,no,h[510][510],s[510][510],head[300010],nxt[1200010],to[1200010],val[1200010],p[510][510];
long long ans,d[300010],dis[110][110],f[110][110];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
void add(int x,int y,int z)
{
	nxt[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=z,nxt[++tot]=head[y],head[y]=tot,to[tot]=x,val[tot]=z;
}
int main()
{
	n=read(),m=read(),T=read();
	for(int i=0;i<=n;i++) for(int j=0;j<=m;j++){
		if(i&&j&&i<n) s[i][j]=read();
		p[i][j]=++np;
	}//这段话的目的其实就是预处理出矩形中每一个点对应的编号
	for(int i=1;i<=n;i++) for(int j=1;j<m;j++) h[i][j]=read();
	while(T--){
		tot=no=0,np=(n+1)*(m+1),ans=0x3f3f3f3f3f3f3f3f,k=read();//多测记得清空
		for(int i=1,w,p,c;i<=k;i++){
			e[i].w=w=read(),e[i].p=p=read(),e[i].c=c=read();
			if(p<=m) s[0][p]=w;
			else if(p<=n+m) h[p-m][m]=w;
			else if(p<=m*2+n) s[n][m*2+n-p+1]=w;
			else h[m*2+n*2-p+1][0]=w;//加入附加点与普通点间的边权
		}
		for(int i=0;i<=n;i++) for(int j=0;j<=m;j++){
			if(j>=1) add(p[i][j-1],p[i][j],s[i][j]);
			if(i>=1) add(p[i-1][j],p[i][j],h[i][j]);
		}//建立出矩形
		sort(e+1,e+k+1),e[k+1]=e[1];//附加点顺时针排序
		for(int i=1;i<=k;i++) if(e[i].c!=e[i+1].c){
			no++;
			for(int j=e[i].p;j<e[i+1].p+(i==k?2*n+2*m:0);j++){
				int J=j%(2*n+2*m);
				if(J<=m) add(p[0][J],np+no,0);
				else if(J<=n+m) add(p[J-m][m],np+no,0);
				else if(J<=m*2+n) add(p[n][m*2+n-J],np+no,0);
				else add(p[m*2+n*2-J][0],np+no,0);
			}//加入两个附加点之间的那个可以作为起、终点的点和连边
		}
		for(int i=1;i<no;i++){
			for(int j=1;j<=np+no;j++) d[j]=ans;
			d[np+i]=0,q.push(make_pair(-d[np+i],np+i));
			while(!q.empty()){
				int x=q.top().second,temp=q.top().first;q.pop();
				if(temp!=-d[x]) continue;
				for(int j=head[x];j;j=nxt[j]) if(d[to[j]]>d[x]+val[j]) d[to[j]]=d[x]+val[j],q.push(make_pair(-d[to[j]],to[j]));
			}
			for(int j=i+1;j<=no;j++) dis[i][j]=dis[i][j+no]=dis[j][i+no]=dis[i+no][j+no]=d[np+j];//要记得是环状的结构所以要开两倍
		}//求最短路，这没什么好说的吧
		for(int i=1;i<=2*no;i++) f[i][i]=ans,f[i][i-1]=0;//记得初始化
		for(int i=2;i<=no;i++) for(int j=1;j+i-1<=2*no;j++){
			int l=j,r=j+i-1;
			f[l][r]=f[l+1][r-1]+dis[l][r];
			for(int p=l+1;p<r;p++) f[l][r]=min(f[l][r],f[l][p]+f[p+1][r]);
			if(i==no) ans=min(ans,f[l][r]);
		}//区间DP求出最优解
		for(int i=1,p,c;i<=k;i++){
			p=e[i].p,c=e[i].c;
			if(p<=m) s[0][p]=0;
			else if(p<=n+m) h[p-m][m]=0;
			else if(p<=m*2+n) s[n][m*2+n-p+1]=0;
			else h[m*2+n*2-p+1][0]=0;
		}//多测清空
		for(int i=1;i<=np+no;i++) head[i]=0;//多测清空
		printf("%lld\n",ans==0x3f3f3f3f3f3f3f3f?0:ans);//记得特判
	}
	return 0;
}
详情
