Page 1 of 1

### Re: 12070 - Invite Your Friends

Posted: Fri Mar 06, 2015 10:24 am
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);
}
}``````