JOI Ninja Contest

JOI Ninja Contestの参加記。

• とりあえず問題を全部読む。
• C実装重そうだけどしっかり書けば満点は余裕そう<-(この時点ですでに敗北は決定していた)
• かく。
• とりあえずdijkstraを4つかく。
• スーパー場合分けターイム！！
• なんだかんだで場合分けしまくる
• バグバグバグ...
• バグバグバグバグ...
• バグバグバグバグバグ...
• なんだかんだでサンプルとおる。これで点取れたら奇跡や
• 10点。
• とりあえず場合分けわかりやすく書き直すか...
• 9点。ファ!?
• オーバーフローとか対策してなかった。
• 16点。

えーいこの関数の順番逆にしてやれ〜(やけっぱち)

• 18点。

• 5時間がこれだけで終了してしまいました。
• AC73個とWA42個が出る気持ち悪い状況に。セット採点恨む。

以下コード。実は10000B超えてる。そりゃ5時間かかるわ。

#include<stdio.h>
#include "stdafx.h"
#include<vector>
#include<algorithm>
#include<queue>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define INF 2100000000000000000LL
typedef long long ll;
typedef pair<ll,ll>pll;
vector<pll>pat[100000];
bool flag[100000];
ll hen(ll a,int gx,int gy)
{
	if(a>=4)
	{
		return a;
	}
	if(gx>=0&&gy>=0)
	{
		return a;
	}
	if(gx>=0&&gy<=0)
	{
		return (a+3)%4;
	}
	if(gx<=0&&gy<=0)
	{
		return (a+2)%4;
	}
	if(gx<=0&&gy>=0)
	{
		return (a+1)%4;
	}
}
pll zhen(ll gx,ll gy)
{
	if(gx>=0&&gy>=0)
	{
		return make_pair(gx,gy);
	}
	if(gx>=0&&gy<=0)
	{
		return make_pair(-gy,gx);
	}
	if(gx<=0&&gy<=0)
	{
		return make_pair(-gx,-gy);
	}
	if(gx<=0&&gy>=0)
	{
		return make_pair(gy,-gx);
	}
}
ll hen2(ll a)
{
	if(a==2)
	{
		return 0;
	}
	if(a==0)
	{
		return 2;
	}
	return a;
}
int main()
{
	ll cit,way,st,gx,gy,gw;
	scanf("%lld%lld%lld%lld%lld%lld",&cit,&way,&st,&gx,&gy,&gw);
	st--;
	gw--;
	for(int i=0;i<way;i++)
	{
		ll za,zb;
		ll zc;
		scanf("%lld%lld%lld",&za,&zb,&zc);
		za--;
		zb--;
		za=hen(hen2(za),gx,gy);
		zb=hen(hen2(zb),gx,gy);
		pat[za].push_back(make_pair(zb,zc));
		pat[zb].push_back(make_pair(za,zc));
	}
	pll z=zhen(gx,gy);
	gx=z.first;
	gy=z.second;
	priority_queue<pll>que;
	que.push(make_pair(0,st));
	fill(flag,flag+cit,0);
	ll moktodoor[4];
	fill(moktodoor,moktodoor+4,INF);
	for(;;)
	{
		if(que.empty())
		{
			break;
		}
		pll zan=que.top();
		que.pop();
		if(moktodoor[0]!=INF&&moktodoor[1]!=INF&&moktodoor[2]!=INF&&moktodoor[3]!=INF)
		{
			break;
		}
		if(flag[zan.second])
		{
			continue;
		}
		flag[zan.second]=true;
		if(zan.second<4)
		{
			moktodoor[zan.second]=-zan.first;
		}
		for(int i=0;i<pat[zan.second].size();i++)
		{
			if(!flag[pat[zan.second][i].first])
			{
				que.push(make_pair(zan.first-pat[zan.second][i].second,pat[zan.second][i].first));
			}
		}
	}
	ll doortodoor[4][4];
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			doortodoor[i][j]=INF;
			if(i==j)
			{
				doortodoor[i][j]=0;
			}
		}
	}
	for(int p=0;p<4;p++)
	{
		priority_queue<pll>pque;
		pque.push(make_pair(0,p));
		fill(flag,flag+cit,false);
		for(;;)
		{
			if(pque.empty())
			{
				break;
			}
			pll zan=pque.top();
			pque.pop();
			if(doortodoor[p][0]!=INF&&doortodoor[p][1]!=INF&&doortodoor[p][2]!=INF&&doortodoor[p][3]!=INF)
			{
				break;
			}
			if(flag[zan.second])
			{
				continue;
			}
			flag[zan.second]=true;
			if(zan.second<4)
			{
				doortodoor[p][zan.second]=-zan.first;
			}
			for(int i=0;i<pat[zan.second].size();i++)
			{
				if(!flag[pat[zan.second][i].first])
				{
					pque.push(make_pair(zan.first-pat[zan.second][i].second,pat[zan.second][i].first));
				}
			}
		}
	}
	priority_queue<pll>qque;
	qque.push(make_pair(0,gw));
	fill(flag,flag+cit,0);
	ll doortomok[4];
	fill(doortomok,doortomok+4,INF);
	for(;;)
	{
		if(qque.empty())
		{
			break;
		}
		pll zan=qque.top();
		qque.pop();
		if(doortomok[0]!=INF&&doortomok[1]!=INF&&doortomok[2]!=INF&&doortomok[3]!=INF)
		{
			break;
		}
		if(flag[zan.second])
		{
			continue;
		}
		flag[zan.second]=true;
		if(zan.second<4)
		{
			doortomok[zan.second]=-zan.first;
		}
		for(int i=0;i<pat[zan.second].size();i++)
		{
			if(!flag[pat[zan.second][i].first])
			{
				qque.push(make_pair(zan.first-pat[zan.second][i].second,pat[zan.second][i].first));
			}
		}
	}/*
	for(int i=0;i<4;i++)
	{
		printf("%lld ",moktodoor[i]);
	}
	printf("\n");
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			printf("%lld ",doortodoor[i][j]);
		}
		printf("\n");
	}
	for(int i=0;i<4;i++)
	{
		printf("%lld ",doortomok[i]);
	}
	printf("\n");*/
	ll mini=INF;
	if(gx==0&&gy==0)
	{		
		priority_queue<pll>rque;
		que.push(make_pair(0,st));
		fill(flag,flag+cit,0);
		for(;;)
		{
			if(rque.empty())
			{
				break;
			}
			pll zan=rque.top();
			rque.pop();
			if(zan.second==gw)
			{
				mini=min(mini,-zan.first);
				break;
			}
			if(flag[zan.second])
			{
				continue;
			}
			flag[zan.second]=true;
			for(int i=0;i<pat[zan.second].size();i++)
			{
				if(!flag[pat[zan.second][i].first])
				{
					rque.push(make_pair(zan.first-pat[zan.second][i].second,pat[zan.second][i].first));
				}
			}
		}
	}
	if(gx==0)
	{
		if(doortodoor[1][3]!=INF)
		{
			mini=min(mini,doortodoor[1][3]*(gy-1)+moktodoor[3]+doortomok[1]);
			if(doortodoor[0][1]!=INF&&doortodoor[0][3]!=INF&&moktodoor[2]!=INF&&doortomok[2]!=INF)
			mini=min(mini,doortodoor[1][3]*(gy-1)+doortodoor[0][1]+doortodoor[0][3]+moktodoor[2]+doortomok[2]);
			if(doortodoor[1][2]!=INF&&doortodoor[2][3]!=INF&&moktodoor[0]!=INF&&doortomok[0]!=INF)
			mini=min(mini,doortodoor[1][3]*(gy-1)+doortodoor[1][2]+doortodoor[2][3]+moktodoor[0]+doortomok[0]);
		}
	}
	if(gy==0)
	{
		if(doortodoor[0][2]!=INF)
		{
			mini=min(mini,doortodoor[0][2]*(gx-1)+moktodoor[2]+doortomok[0]);
			if(doortodoor[0][1]!=INF&&doortodoor[1][2]!=INF&&moktodoor[3]!=INF&&doortomok[3]!=INF)
			mini=min(mini,doortodoor[0][2]*(gx-1)+doortodoor[0][1]+doortodoor[1][2]+moktodoor[3]+doortomok[3]);
			if(doortodoor[0][3]!=INF&&doortodoor[2][3]!=INF&&moktodoor[1]!=INF&&doortomok[1]!=INF)
			mini=min(mini,doortodoor[0][2]*(gx-1)+doortodoor[0][3]+doortodoor[2][3]+moktodoor[1]+doortomok[1]);
		}
	}/*
	if(gx<gy)
	{
		mini=min(mini,moktodoor[1]+doortomok[3]+gx*(doortodoor[2][3]+doortodoor[0][1])+(gy-gx-1)*(doortodoor[1][3]));
	}
	else
	{
		mini=min(mini,moktodoor[1]+doortomok[3]+(gy-1)*(doortodoor[2][3]+doortodoor[0][1])+(gx-gy+1)*(doortodoor[0][2]));
	}
	mini=min(mini,moktodoor[1]+doortomok[3]+1*(doortodoor[2][3]+doortodoor[0][1])+(gy-2)*(doortodoor[1][3])+(gx-1)*(doortodoor[0][2]));
	if(gx>gy)
	{
		mini=min(mini,moktodoor[0]+doortomok[2]+gy*(doortodoor[0][3]+doortodoor[1][2])+(gx-gy-1)*(doortodoor[0][2]));
	}
	else
	{
		mini=min(mini,moktodoor[0]+doortomok[2]+(gx-1)*(doortodoor[0][3]+doortodoor[1][2])+(gy-gx+1)*(doortodoor[1][3]));
	}
	mini=min(mini,moktodoor[0]+doortomok[2]+1*(doortodoor[0][3]+doortodoor[1][2])+(gy-1)*(doortodoor[1][3])+(gx-2)*(doortodoor[0][2]));
	if(gx<gy)
	{
		mini=min(mini,moktodoor[1]+doortomok[0]+gx*doortodoor[2][3]+(gx-1)*doortodoor[0][1]+(gy-gx)*(doortodoor[1][3]));
	}
	else
	{
		mini=min(mini,moktodoor[1]+doortomok[0]+(gy-1)*doortodoor[2][3]+gy*doortodoor[0][1]+(gx-gy)*(doortodoor[0][2]));
	}
	mini=min(mini,moktodoor[1]+doortomok[0]+2*doortodoor[2][3]+1*doortodoor[0][1]+(gy-2)*(doortodoor[1][3])+(gx-2)*(doortodoor[0][2]));
	if(gx>gy)
	{
		mini=min(mini,moktodoor[2]+doortomok[3]+gy*doortodoor[0][1]+(gy-1)*doortodoor[2][3]+(gx-gy)*(doortodoor[0][2]));
	}
	else
	{
		mini=min(mini,moktodoor[2]+doortomok[3]+(gx-1)*doortodoor[0][1]+gx*doortodoor[2][3]+(gy-gx)*(doortodoor[1][3]));
	}
	mini=min(mini,moktodoor[2]+doortomok[3]+1*doortodoor[2][3]+2*doortodoor[0][1]+(gy-2)*(doortodoor[1][3])+(gx-2)*(doortodoor[0][2]));*/
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			ll dx=gx,dy=gy;
			ll zei=moktodoor[i]+doortomok[j];
			if(moktodoor[i]==INF||doortomok[j]==INF)
			{
				continue;
			}
			int frm=i,to=j;
			if(i==0)
			{
				if(doortodoor[1][2]==INF)
				{
					continue;
				}
				zei+=doortodoor[1][2];
				dx++;
				frm=1;
			}
			if(i==3)
			{
				if(doortodoor[1][2]==INF)
				{
					continue;
				}
				zei+=doortodoor[1][2];
				dy++;
				frm=2;
			}
			if(j==1)
			{
				if(doortodoor[0][3]==INF)
				{
					continue;
				}
				zei+=doortodoor[0][3];
				dy++;
				to=0;
			}
			if(j==2)
			{
				if(doortodoor[0][3]==INF)
				{
					continue;
				}
				zei+=doortodoor[0][3];
				dx++;
				to=3;
			}
			if(dx<0||dy<0)
			{
				continue;
			}
			if(frm==1&&to==3)
			{
				if(dy-dx+1>0)
				{
					if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[0][2]!=INF&&dy>=1)
					mini=min(mini,zei+(dy-1)*(doortodoor[0][1]+doortodoor[2][3])+(dy-dx+1)*doortodoor[0][2]);
				}
				else
				{
					if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[1][3]!=INF&&dx>=1)
					mini=min(mini,zei+(dx-1)*(doortodoor[0][1]+doortodoor[2][3])+(-dy+dx-1)*doortodoor[1][3]);
				}
				if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[0][2]!=INF&&doortodoor[1][3]!=INF&&dy>=2&&dx>=1)
				mini=min(mini,zei+doortodoor[0][1]+doortodoor[2][3]+(dx-1)*doortodoor[0][2]+(dy-2)*doortodoor[1][3]);
			}
			if(frm==2&&to==0)
			{
				if(dx-dy+1>0)
				{
					if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[1][3]!=INF&&dx>=1)
					mini=min(mini,zei+(dx-1)*(doortodoor[0][1]+doortodoor[2][3])+(dx-dy+1)*doortodoor[1][3]);
				}
				else
				{
					if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[0][2]!=INF&&dy>=1)
					mini=min(mini,zei+(dy-1)*(doortodoor[0][1]+doortodoor[2][3])+(-dx+dy-1)*doortodoor[0][2]);
				}
				if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[0][2]!=INF&&doortodoor[1][3]!=INF&&dy>=1&&dx>=2)
				mini=min(mini,zei+doortodoor[0][1]+doortodoor[2][3]+(dx-2)*doortodoor[0][2]+(dy-1)*doortodoor[1][3]);
			}
			if(frm==1&&to==0)
			{
				if(dy-dx>0)
				{
					if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[0][2]!=INF&&dx>=1)
					mini=min(mini,zei+dx*doortodoor[2][3]+(dx-1)*doortodoor[0][1]+(dy-dx)*doortodoor[0][2]);
				}
				else
				{
					if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[1][3]!=INF&&dy>=1)
					mini=min(mini,zei+dy*doortodoor[2][3]+(dy-1)*doortodoor[0][1]+(dx-dy)*doortodoor[1][3]);
				}
				if(doortodoor[2][3]!=INF&&doortodoor[0][2]!=INF&&doortodoor[1][3]!=INF&&dy>=1&&dx>=1)
				mini=min(mini,zei+doortodoor[2][3]+(dx-1)*doortodoor[1][3]+(dy-1)*doortodoor[0][2]);
			}
			if(frm==2&&to==3)
			{
				if(dx-dy>0)
				{
					if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[1][3]!=INF&&dy>=1)
					mini=min(mini,zei+dy*doortodoor[0][1]+(dy-1)*doortodoor[2][3]+(dx-dy)*doortodoor[1][3]);
				}
				else
				{
					if(doortodoor[0][1]!=INF&&doortodoor[2][3]!=INF&&doortodoor[0][2]!=INF&&dx>=1)
					mini=min(mini,zei+dx*doortodoor[0][1]+(dx-1)*doortodoor[2][3]+(dy-dx)*doortodoor[0][2]);
				}
				if(doortodoor[0][1]!=INF&&doortodoor[0][2]!=INF&&doortodoor[1][3]!=INF&&dy>=1&&dx>=1)
				mini=min(mini,zei+doortodoor[0][1]+(dx-1)*doortodoor[1][3]+(dy-1)*doortodoor[0][2]);
			}
		}

	}



	if(mini>=INF)
	{
		printf("-1\n");
	}
	else
	{
		printf("%lld\n",mini);
	}
	return 0;
}

Aはちゃんとやれば解けた気がする。
結論:実装量をちゃんと考えてから問題に挑みましょう。