안녕하세요. 과제에 명시된대로 일체의 외부 라이브러리를 사용하지 않고 C의 기본 기능만을 이용해 다익스트라 알고리즘을 작성하고 있습니다. 그런데 일부 케이스에 대해서, WA가 발생하는 것을 볼 수 있었습니다. 이 원인에 대해서 알고 싶습니다. 이하는 제가 사용한 코드입니다.
#include <stdio.h>
#include <stdlib.h>
#define INF 10e8
typedef struct _V
{
int to[1100];
int w[1100];
int p;
int d;
int n;
char s[110];
};
typedef struct _V V;
V *pq[2010], G[2010];
int dist[20100], addr[20100];
int pq_size, map_size, v, e, tp;
char str[1010], *loc, map[20100][20];
int cmp_str(char *s1, char *s2)
{
for(int i = 0; ; i++) {
if(s1[i] < s2[i]) return -1;
else if(s1[i] > s2[i]) return 1;
if(!s1[i] && !s2[i]) break;
}
return 0;
}
void map_str(char *s1)
{
int i;
for(i = 0; s1[i]; i++)
map[map_size][i] = s1[i];
map[map_size][i] = 0;
map_size++;
}
int map_find(char *s1)
{
for(int i = 0; i < map_size; i++) {
if(!cmp_str(map[i], s1)) return i;
}
return -1;
}
void ex_v(int x, int y)
{
V *tmp;
int taddr;
taddr = addr[pq[x]->n];
addr[pq[x]->n] = addr[pq[y]->n];
addr[pq[y]->n] = taddr;
tmp = pq[x];
pq[x] = pq[y];
pq[y] = tmp;
}
void min_heapify(int k)
{
int l = k * 2;
int r = k * 2 + 1;
int min;
if(l <= pq_size && pq[l]->d < pq[k]->d)
min = l;
else if(l <= pq_size && pq[l]->d == pq[k]->d && cmp_str(pq[l]->s, pq[k]->s) < 0)
min = l;
else min = k;
if(r <= pq_size && pq[r]->d < pq[min]->d)
min = r;
else if(r <= pq_size && pq[r]->d == pq[min]->d && cmp_str(pq[r]->s, pq[min]->s) < 0)
min = r;
else min = min;
if(min != k) {
ex_v(min, k);
min_heapify(min);
}
}
V *pq_extract_min()
{
V *tmp = pq[1];
pq[1] = pq[pq_size];
pq_size--;
min_heapify(1);
return tmp;
}
void pq_dec_key(int pos, int key)
{
int i = addr[pos];
pq[i]->d = key;
while(i > 1 && pq[i / 2]->d >= pq[i]->d) {
if(pq[i / 2]->d == pq[i]->d && cmp_str(pq[i / 2]->s, pq[i]->s) < 0)
break;
ex_v(i / 2, i);
i /= 2;
}
}
void push_back(V *v, int i, int k)
{
v->to[v->p] = i;
v->w[v->p] = k;
v->p += 1;
}
void pq_build()
{
for(int i = pq_size / 2; i > 0; i--)
min_heapify(i);
}
int main()
{
pq_size = 1;
map_size = 0;
scanf("%s", str);
scanf("%d", &e);
loc = str;
for(int i = 0; str[i]; i++)
if(str[i] == ',') pq_size++, str[i] = 0;
v = pq_size;
for(int i = 0; i < pq_size; i++) {
V *telem = &G[i];
for(int j = 0; j < 110; j++) {
telem->to[j] = 0;
telem->w[j] = 0;
}
telem->p = 0;
telem->d = INF;
telem->n = i;
int pos = 0;
while(*loc)
telem->s[pos++] = *loc, loc++;
telem->s[pos] = 0;
map_str(telem->s);
loc++;
// printf("%s\n", telem->s);
pq[i + 1] = telem;
addr[i] = i + 1;
dist[i] = INF;
}
pq_build();
for(int i = 0; i < e; i++) {
scanf("%s", str);
char *lp[3];
lp[0] = str;
int tp = 1;
for(int j = 0; str[j]; j++) {
if(str[j] == ',') lp[tp++] = &str[j + 1], str[j] = 0;
}
int st, ed;
st = map_find(lp[0]);
ed = map_find(lp[1]);
int tmp = 0;
for(char *j = lp[2]; *j; j++) {
tmp *= 10;
tmp += (*j) - '0';
}
// printf("%d -> %d, w: %d\n", st, ed, tmp);
push_back(&G[st], ed, tmp);
}
/*
for(int i = 0; i < v; i++) {
for(int j = 0; j < G[i].p; j++) {
printf("%d -> %d, %d\n", i, G[i].to[j], G[i].w[j]);
}
}
*/
pq_dec_key(0, 0);
dist[0] = 0;
while(pq_size != 0) {
int cur = pq_extract_min()->n;
for(int i = 0; i < G[cur].p; i++) {
if(dist[G[cur].to[i]] > dist[cur] + G[cur].w[i]) {
dist[G[cur].to[i]] = dist[cur] + G[cur].w[i];
pq_dec_key(G[cur].to[i], dist[G[cur].to[i]]);
}
}
}
for(int i = 0; i < v; i++) {
printf("%d", dist[i]);
if(i != v - 1) putchar('\n');
}
}
PS. Input 형식이 타 저지 사이트의 유사 문제에 비해서 많이 까다롭네요...
PS2. V, E의 범위에 대한 내용도 추가해주셨으면 좋겠습니다.
PS3. Vertex들의 이름이 한 글자가 아닌 문자열이 올 수도 있는 것인지 확신을 얻고 싶습니다.