Submission #656741

#	Time	Username	Problem	Language	Result	Execution time	Memory
656741		haojiandan	Wild Boar (JOI18_wild_boar)	C++14	62 / 100	18053 ms	469376 KiB

wild_boar

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const ll INF=1e18;
const int maxn=4010;
int n,m;
int Q,L;
ll dis[maxn][maxn],w[maxn];
pair<int,int> E[maxn];
ll mn[maxn][maxn][5];
pair<int,int> rem[maxn][maxn][5];
vector<int> in[maxn],out[maxn];
int id[maxn][maxn]; bool vis[maxn];
int d[maxn]; ll dp[2][maxn];
priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > > q;
int main() {
	read(n),read(m);
	read(Q),read(L);
	int tot=0;
	for (int i=1;i<=m;i++) {
		int x,y; read(x),read(y);
		id[x][y]=id[y][x]=i;
		read(w[i]);
		
		E[tot]=MP(x,y);
		out[x].push_back(tot),in[y].push_back(tot);
		tot++;
		E[tot]=MP(y,x);
		out[y].push_back(tot),in[x].push_back(tot);
		tot++;
	}
	for (int i=0;i<tot;i++) {
		q.push(MP(0,i));
		for (int j=0;j<tot;j++) dis[i][j]=INF,vis[j]=0;
		dis[i][i]=0;
		while (!q.empty()) {
			int x=q.top().second; q.pop();
			if (vis[x]) continue;
			vis[x]=1;
			int u=E[x].second;
			for (int &id : out[u]) {
				int v=E[id].second;
				if ((id^x)==1) continue;
				assert(id!=x);
				ll w=::w[::id[u][v]];
				assert(id/2+1==::id[u][v]);
				if (dis[i][id]>dis[i][x]+w) dis[i][id]=dis[i][x]+w,q.push(MP(dis[i][id],id));
			}
		}
	}
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j) {
		ll *mn=::mn[i][j];
		pair<int,int> *rem=::rem[i][j];
		for (int k=0;k<5;k++) mn[k]=INF;
		for (int k=0;k<5;k++) {
			for (int &x : out[i]) for (int &y : in[j]) {
				if (dis[x][y]+w[x/2+1]<mn[k]) {
					int A=E[x].second,B=E[y].first;
					if (k==1&&A==rem[0].first) continue;
					if (k==2&&(A==rem[0].first||B==rem[1].second)) continue;
					if (k==3&&B==rem[0].second) continue;
					if (k==4&&(B==rem[0].second||A==rem[3].first)) continue;
					mn[k]=dis[x][y]+w[x/2+1];
					rem[k]=MP(A,B);
				}
			}
			if (id[i][j]&&w[id[i][j]]<mn[k]) {
				int A=j,B=i;
				if (k==1&&A==rem[0].first) continue;
				if (k==2&&(A==rem[0].first||B==rem[1].second)) continue;
				if (k==3&&B==rem[0].second) continue;
				if (k==4&&(B==rem[0].second||A==rem[3].first)) continue;
				mn[k]=w[id[i][j]];
				rem[k]=MP(A,B);
			}
		}
	}
	for (int i=1;i<=L;i++) read(d[i]);
	while (Q--) {
		int x; read(x),read(d[x]);
		int op=0;
		for (int i=0;i<5;i++) dp[op][i]=mn[d[1]][d[2]][i];
	//	printf("%lld %d\n",mn[2][1][1],rem[2][1][1].second);
		for (int i=3;i<=L;i++) {
			for (int j=0;j<5;j++) dp[op^1][j]=INF;
			for (int j=0;j<5;j++) for (int k=0;k<5;k++) if (mn[d[i-1]][d[i]][k]<INF) {
				if (rem[d[i-2]][d[i-1]][j].second==rem[d[i-1]][d[i]][k].first) continue;
				dp[op^1][k]=min(dp[op^1][k],dp[op][j]+mn[d[i-1]][d[i]][k]);
			}
			op^=1;
		}
		ll ans=INF;
		for (int j=0;j<5;j++) ans=min(ans,dp[op][j]);
		if (ans==INF) ans=-1;
		printf("%lld\n",ans);
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 0 / 38