XMOJ3065 旅游线路-Code

#include<bits/stdc++.h>
using namespace std;

const int N=40000+5,M=1e5+5,INF=1e9;

int n,m,k,ans,a[N],b[N],f[N][2];

struct giao{
	int a,b;
}c[M];

bool cmp(giao x,giao y){
	return x.a!=y.a?x.a<y.a:x.b<y.b; 
}

int main(){
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		f[i][0]=a[i];
		ans=max(ans,a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&b[i]);
		f[i][1]=b[i];
		ans=max(ans,b[i]);
	}
	for(int i=1;i<=k;i++)
		scanf("%d%d",&c[i].a,&c[i].b);
	sort(c+1,c+1+k,cmp);
	for(int i=1;i<=k;i++){
		int sa=f[c[i].b][1]+a[c[i].a],sb=f[c[i].a][0]+b[c[i].b];
		f[c[i].a][0]=max(f[c[i].a][0],sa);
		f[c[i].b][1]=max(f[c[i].b][1],sb);
		ans=max(ans,max(f[c[i].a][0],f[c[i].b][1]));
	}
	printf("%d",ans);
	return 0;
}