いろはちゃんコンテスト Day2 : I - 南極

これは想定解より別解が楽だな。
https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_i

問題

グリッドが与えられる。
一部のマスは氷山で占有されている。
各氷山は複数の連結マスから構成される。

各氷山を破壊するのに必要なコストが与えられたとき、指定された始点から終点に到達するコストを最小化せよ。

解法

実は連結とか気にしなくても解くことができる。
ダイクストラ法をする際、「移動元と移動先がが同一の氷山に占められるときはコスト0」とすれば、あとは単純なダイクストラ法で済む。

int H,W,X;
int SX,SY,GX,GY;
ll A[505][505];
ll C[505050];
ll dist[505][505];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>X;
	cin>>SY>>SX>>GY>>GX;
	SY--,SX--,GY--,GX--;
	FOR(y,H) FOR(x,W) cin>>A[y][x], dist[y][x]=1LL<<60;
	for(i=1;i<=X;i++) cin>>C[i];
	
	dist[SY][SX]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,SY*1000+SX});
	
	while(Q.size()) {
		ll co=-Q.top().first;
		int cy=Q.top().second/1000;
		int cx=Q.top().second%1000;
		Q.pop();
		if(dist[cy][cx]!=co) continue;
		
		FOR(i,4) {
			int dd[4]={1,0,-1,0};
			int ty=cy+dd[i];
			int tx=cx+dd[i^1];
			if(ty<0||ty>=H||tx<0||tx>=W) continue;
			
			if(A[cy][cx]==A[ty][tx]) {
				if(dist[ty][tx]>co) {
					dist[ty][tx]=co;
					Q.push({-co,ty*1000+tx});
				}
			}
			else {
				if(dist[ty][tx]>co+C[A[ty][tx]]) {
					dist[ty][tx]=co+C[A[ty][tx]];
					Q.push({-dist[ty][tx],ty*1000+tx});
				}
			}
		}
		
	}
	
	cout<<dist[GY][GX]<<endl;
}

まとめ

この別解は想定外だったのか…？