Hi guys,
I’m stuck on TSHPATH/SHPATH problems. Got WA with many attempts. I’ve checked my code for boundary cases and large input, I’ve also checked this code on the similar problems (uva-judge uva-929, uva-1112, uva-10986) and everything was fine. Need any help/test cases.
I use dijsktra + priority queue. Priority queue code was copy-pasted from Sedgwick’s book. Thank you!
Code:
#undef NDEBUG
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
struct PQi {
int d;
int N;
int* pq;
int* qp;
int* a;
};
void pq_fixUp(struct PQi* self, int k);
void pq_exch(struct PQi* self, int i, int j);
void pq_fixDown(struct PQi* self, int k, int n);
void pq_init(struct PQi* self, int N, int* keys, int d) {
self->d = d;
self->N = 0;
self->a = keys;
self->pq = malloc((N+1)*sizeof(int));
self->qp = malloc((N+1)*sizeof(int));
}
void pq_destroy(struct PQi* self) {
free(self->pq);
free(self->qp);
}
void pq_insert(struct PQi* self, int v) {
self->pq[++(self->N)] = v;
self->qp[v] = self->N;
pq_fixUp(self, self->N);
}
int pq_getmin(struct PQi* self) {
pq_exch(self, 1, self->N);
pq_fixDown(self, 1, self->N-1);
return self->pq[self->N--];
}
void pq_lower(struct PQi* self, int k) {
pq_fixUp(self, self->qp[k]);
}
void pq_exch(struct PQi* self, int i, int j) {
int t;
t = self->pq[i]; self->pq[i] = self->pq[j]; self->pq[j] = t;
self->qp[self->pq[i]] = i;
self->qp[self->pq[j]] = j;
}
void pq_fixUp(struct PQi* self, int k) {
int* a = self->a;
int d = self->d;
int* pq = self->pq;
while ((k > 1) && (a[pq[(k+d-2)/d]] > a[pq[k]])) {
pq_exch(self, k, (k+d-2)/d);
k = (k+d-2)/d;
}
}
void pq_fixDown(struct PQi* self, int k, int n) {
int d = self->d;
int* pq = self->pq;
int* a = self->a;
int i, j;
while ((j = (d*(k-1)+2)) <= n) {
for (i = j+1; i<j+d && i <= n; i=i+1) {
if (a[pq[j]] > a[pq[i]]) {
j = i;
}
}
if (!(a[pq[k]] > a[pq[j]])) {
break;
}
pq_exch(self, k, j);
k = j;
}
}
void pq_info(struct PQi* self) {
printf("info\n");
printf("pq:\n");
for (int i = 1; i <= self->N; i=i+1) {
printf("%d ", self->pq[i]);
}
printf("qp:\n");
for (int i = 1; i <= self->N; i=i+1) {
printf("%d ", self->pq[i]);
}
printf("end of info\n");
}
void pq_test() {
struct PQi pq;
int keys[] = {0 /*unused*/,1,2,3,4,5,5,4,3,2,1};
pq_init(&pq, 200, keys, 2);
for (int i = 1; i<=10; i=i+1) {
printf("insert %d\n", i);
pq_insert(&pq, i);
pq_info(&pq);
}
for (int i = 1; i<=6; i=i+1) {
int m = pq_getmin(&pq);
printf("min => %d\n", m);
}
}
int find_index(char* id2name, int n, char* name) {
for (int i = 1; i<=n; i=i+1) {
if (!strcmp(&id2name[i*20], name)) {
return i;
}
}
return -200000;
}
int find_mincost(int*W, int*Links, int*Sizes, int n, int rs, int i1, int i2) {
struct PQi pq;
int* R;
int* P;
int IntMax = INT_MAX - 200000;
int i,j1,j,kMin,res,wt;
R = malloc((n+1)*sizeof(int));
P = malloc((n+1)*sizeof(int));
for (int i = 1; i<=n; i=i+1) {
P[i] = 1;
R[i] = IntMax;
}
for (i = 1; i <= Sizes[i1]; i=i+1) {
R[Links[i1*rs+i]] = W[i1*rs+i];
}
R[i1] = 0;
pq_init(&pq, n+1, R, 2);
for (i=1; i<=n; i=i+1) {
pq_insert(&pq, i);
}
kMin = pq_getmin(&pq);
assert(kMin == i1);
R[i1] = 0;
P[i1] = 0;
for (i=1; i<=n-1; i=i+1) {
kMin = pq_getmin(&pq);
for (j1=1;j1<=Sizes[kMin];j1=j1+1) {
j = Links[kMin*rs+j1];
wt = W[kMin*rs+j1];
if (R[kMin]+wt < R[j]) {
R[j] = R[kMin]+wt;
P[j] = kMin;
pq_lower(&pq, j);
}
}
}
res = R[i2];
if (res == IntMax) {
res = -1;
}
pq_destroy(&pq);
free(R); free(P);
return res;
}
void solve() {
int n,rs;
int k,i,j,nr,cost;
int* W;
int* Links;
int* Sizes;
char* id2name;
char name1[20];
char name2[20];
scanf("%d", &n);
rs = n+10;
W = malloc((n+1)*rs*sizeof(int));
Links = malloc((n+1)*rs*sizeof(int));
Sizes = calloc((n+1),sizeof(int));
id2name = malloc(20*(n+1));
for (i = 1; i<=n; i=i+1) {
scanf("%s", &id2name[20*i]);
scanf("%d", &k);
for (j = 1; j<=k; j=j+1) {
scanf("%d%d", &nr, &cost);
Sizes[i]++;
Links[i*rs+Sizes[i]] = nr;
W[i*rs+Sizes[i]] = cost;
}
}
scanf("%d",&nr);
for (i=1; i<=nr; i=i+1) {
scanf("%s%s", name1, name2);
int i1= find_index(id2name, n, name1);
int i2= find_index(id2name, n, name2);
// printf("search %d->%d: '%s'->'%s'\n", i1,i2, name1, name2);
cost = find_mincost(W,Links,Sizes,n,rs,i1,i2);
if (cost >= 0) {
printf("%d\n", cost);
}
}
free(W); free(Links); free(Sizes); free(id2name);
}
int main() {
// pq_test();
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
