#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000
#define M 1000
#define L 20
#define INF 0x3f3f3f3f3f3f3f3fLL
char ss[N][L + 1];
int *ej[N], *ew[N], eo[N], n;
int idx(char *s) {
int i;
for (i = 0; i < n; i++)
if (strcmp(ss[i], s) == 0)
return i;
strcpy(ss[n], s);
ej[n] = (int *) malloc(2 * sizeof *ej[n]);
ew[n] = (int *) malloc(2 * sizeof *ew[n]);
return n++;
}
void append(int i, int j, int w) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0) {
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
}
ej[i][o] = j, ew[i][o] = w;
}
long long *dd_; int pq[N], iq[1 + N], cnt;
int lt(int i, int j) { return dd_[i] < dd_[j]; }
int p2(int p) {
return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add_last(int i) {
iq[pq[i] = ++cnt] = i;
}
int pq_remove_first() {
int i = iq[1], j = iq[cnt--];
if (j != i)
pq[j] = 1, pq_dn(j);
pq[i] = 0;
return i;
}
void dijkstra(long long *dd, int i) {
memset(dd, 0x3f, n * sizeof *dd), dd_ = dd;
dd[i] = 0, pq_add_last(i);
while (cnt) {
int o;
i = pq_remove_first();
for (o = eo[i]; o--; ) {
int j = ej[i][o];
long long d = dd[i] + ew[i][o];
if (dd[j] > d) {
if (dd[j] == INF)
pq_add_last(j);
dd[j] = d, pq_up(j);
}
}
}
}
int main() {
static long long dd[N][N];
int m, q, h, i, j;
scanf("%d%d", &n, &m);
for (h = 0; h < m; h++) {
static char s[L + 1], t[L + 1];
int w;
scanf("%s%s%d", s, t, &w), i = idx(s), j = idx(t);
append(i, j, w);
}
scanf("%d", &q);
for (i = 0; i < n; i++)
dijkstra(dd[i], i);
while (q--) {
static char s[L + 1], t[L + 1];
scanf("%s%s", s, t), i = idx(s), j = idx(t);
if (dd[i][j] == INF)
printf("Roger\n");
else
printf("%lld\n", dd[i][j]);
}
return 0;
}
Compilation message
alias.c: In function 'append':
alias.c:28:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
28 | if (o >= 2 && (o & o - 1) == 0) {
| ~~^~~
alias.c: In function 'main':
alias.c:96:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
alias.c:101:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%s%s%d", s, t, &w), i = idx(s), j = idx(t);
| ^~~~~~~~~~~~~~~~~~~~~~~~~
alias.c:104:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
alias.c:110:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | scanf("%s%s", s, t), i = idx(s), j = idx(t);
| ^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
844 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1444 KB |
Output is correct |
| 5 |
Runtime error |
25 ms |
16424 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
23 ms |
14996 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
25 ms |
16440 KB |
Execution killed with signal 11 |
