UVa 11997 K Smallest Sums/優先キュー

ゆうせんキュー
n行各行n個の数字各行に1個の和を求める最小のn個を選択する
2行しかないとします
行ごとにソート
a1 a2 a3 ... an
b1 b2 b3 ... bn
a 1+b 1,a 2+b 1,a 3+b 1,...,an+b 1エンキュー
次に、最小(pop)を取り出し、ax+byであれば、n個を取り出して配列cに格納するまでax+b(y+1)(push)を入れる.
nがあれば、最初の行と2番目の行を2つマージした結果を3番目の行とマージできます...

#include <cstdio>
#include <queue>
#include <cstring> 
#include <algorithm>
const int maxn = 800;
using namespace std;

int a[maxn][maxn];
struct Item
{
	int s;
	int b; 
	Item(int s, int b):s(s), b(b) {}
	bool operator < (const Item& rhs) const
	{
		return s > rhs.s;
	}	
};
int n;

void merge(int* A, int* B, int* C)
{
	 priority_queue <Item> q;
	 for(int i = 0; i < n; i++)
	 	q.push(Item(A[i]+B[0], 0));
	 for(int i = 0; i < n; i++)
	 {
	 	Item item = q.top();
	 	q.pop();
	 	C[i] = item.s;
	 	int b = item.b;
	 	if(b+1 < n)
	 	q.push(Item(item.s-B[b]+B[b+1], b+1)); 
	 }
}		  
int main()
{
	int i, j; 
	while(scanf("%d", &n) == 1)
	{
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
				scanf("%d", &a[i][j]);
			sort(a[i], a[i]+n);
		}
		for(i = 1; i < n; i++)
			merge(a[0], a[i], a[0]);
		printf("%d",a[0][0]);
		for(i = 1; i < n; i++)
			printf(" %d", a[0][i]); 
		printf("
");
	}
	return 0;
}