Re: 12070 - Invite Your Friends

[bbb60]

hi,...
I'm trying it by Dijkstra with Constraint and test by a lot of test case in uDebug and that is true, but i get Wrong Answer in uva.
who help me why that?

Code: Select all

#include<iostream>
#include <stdio.h>
#include <limits.h>
#include <cmath>
#include <stdio.h>
using namespace std;

#define V 625
#define INF INT_MAX
#define DT int



int minW1(DT w1[], bool sptSet[],int n)
{
	int min = INF, min_index;
	for (int v = 0; v < n; v++)
		if (sptSet[v] == false && w1[v] <= min)
			min = w1[v], min_index = v;
	return min_index;
}
void dijk(DT g1[][V], DT g2[][V], int src, int n, DT cns, DT w1[])
{
	//DT w1[V];
	DT w2[V] = { 0 };
	bool sptSet[V] = { 0 };
	for (int i = 0; i < n; i++)
		w1[i] = g1[src][i], w2[i]= g1[src][i]==INF ? 0 : 1;

	w1[src] = 0;
	for (int count = 0; count < n - 1; count++)
	{
		int u = minW1(w1, sptSet,n);
		sptSet[u] = true;
		for (int v = 0; v < n; v++)
			if (w1[u] - INF && !sptSet[v] && g1[u][v] - INF)
				if (w2[u] + g2[u][v] <= cns && w1[u] + g1[u][v] < w1[v])
				{
					w1[v] = w1[u] + g1[u][v];
					w2[v] = w2[u] + g2[u][v];
				}

	}
	
}



int g1[V][V], g2[V][V], dist[5][V];
int main()
{
	int n, f, t, casi = 1;
	for (; cin >> n >> f >> t && (n || f || t); casi++)
	{


		int size = n*n;

		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				g1[i][j] = INF, g2[i][j] = 1;

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				int val, u, d, l, r, cur;	//up, down, left, right
				cin >> val;
				cur = n*i + j;
				u = cur - n;	if (i > 0)		g1[cur][u] = val;
				d = cur + n;	if (i < n - 1)	g1[cur][d] = val;
				l = cur - 1;	if (j > 0)		g1[cur][l] = val;
				r = cur + 1;	if (j < n - 1)	g1[cur][r] = val;
			}
		}
		for (int i = 0; i < f; i++)
		{
			int x, y;
			cin >> x >> y;
			dijk(g1, g2, x*n + y, size, t, dist[i]);
		}
		int rafiqX, rafiqy;
		long long minT = 999999999;
		for (int i = 0; i < size; i++)
		{
			long long sum = 0;
			for (int j = 0; j < f; j++)
			{
				if (dist[j][i] - INF)
					sum += dist[j][i];
				else
				{
					sum = -1;
					break;
				}
			}
			if (sum + 1 && sum<minT)
			{
				minT = sum;
				int rafiqI;
				rafiqI = i;
				rafiqX = rafiqI / n;
				rafiqy = rafiqI - rafiqX*n;
			}
		}
		
		if (minT != 999999999)
			printf("Case #%d: Selected city (%d,%d) with minimum cost %lld.\n", casi, rafiqX, rafiqy, minT);
		else printf("Case #%d: Impossible.\n", casi);
	}
}