fork(1) download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define inf 0x7fFFffFF
  5.  
  6. short nodes, paths, chs;
  7. short** plst, * viz, * ord, * pord;
  8. unsigned int*** list, * dist, * globd;
  9. char** name;
  10.  
  11. inline int cmp(const void* a, const void* b)
  12. {
  13.     return strcmp(name[*((const short*)a)], name[*((const short*)b)]);
  14. }
  15.  
  16. inline int comp(const void* a, const void* b)
  17. {
  18.     return plst[*((const short*)a)][chs] - plst[*((const short*)b)][chs];
  19. }
  20.  
  21. short getindex(const char* string)
  22. {
  23.     short lo = 1, hi = nodes, mid, res;
  24.     while (lo <= hi) {
  25.         mid = (lo + hi) / 2;
  26.         res = strcmp(string, name[ord[mid]]);
  27.         if (!res) {
  28.             return ord[mid];
  29.         } else if (res > 0) {
  30.             lo = mid + 1;
  31.         } else {
  32.             hi = mid - 1;
  33.         }
  34.     }
  35.     return 0;
  36. }
  37.  
  38. void read()
  39. {
  40.     short i, j, nbs, nb;
  41.     unsigned int cst;
  42.     char tmp[11];
  43.     scanf("%hd", &nodes);
  44.     name = (char**) malloc((nodes + 1) * sizeof(char*));
  45.     ord = (short*) malloc((nodes + 1) * sizeof(short));
  46.     list = (unsigned int***) malloc((nodes + 1) * sizeof(unsigned int**));
  47.     for (i = 1; i <= nodes; ++i) {
  48.         scanf("%s\n%hd", tmp, &nbs);
  49.         name[i] = (char*) malloc((strlen(tmp) + 1) * sizeof(char));
  50.         ord[i] = i;
  51.         strcpy(name[i], tmp);
  52.         list[i] = (unsigned int**) malloc((nbs + 1) * sizeof(unsigned int*));
  53.         list[i][0] = (unsigned int*) malloc(sizeof(unsigned int));
  54.         list[i][0][0] = nbs;
  55.         for (j = 1; j <= nbs; ++j) {
  56.             scanf("%hd %u", &nb, &cst);
  57.             list[i][j] = (unsigned int*) malloc(2 * sizeof(unsigned int));
  58.             list[i][j][0] = nb;
  59.             list[i][j][1] = cst;
  60.         }
  61.     }
  62.     qsort(ord + 1, nodes, sizeof(short), cmp);
  63.     scanf("%hd", &paths);
  64.     plst = (short**) malloc(paths * sizeof(short*));
  65.     pord = (short*) malloc(paths * sizeof(short));
  66.     globd = (unsigned int*) malloc(paths * sizeof(unsigned int));
  67.     for (i = 0; i < paths; ++i) {
  68.         plst[i] = (short*) malloc(2 * sizeof(short));
  69.         pord[i] = i;
  70.         scanf("%s", tmp);
  71.         plst[i][0] = getindex(tmp);
  72.         scanf("%s", tmp);
  73.         plst[i][1] = getindex(tmp);
  74.     }
  75.     viz = (short*) malloc((nodes + 1) * sizeof(short));
  76.     dist = (unsigned int*) malloc((nodes + 1) * sizeof(unsigned int));
  77. }
  78.  
  79. short getoptim()
  80. {
  81.     short maxs, maxd, i, * vecs, * vecd;
  82.     maxs = maxd = 0;
  83.     vecs = (short*) calloc(nodes + 1, sizeof(short));
  84.     vecd = (short*) calloc(nodes + 1, sizeof(short));
  85.     for (i = 0; i < paths; ++i) {
  86.         ++vecs[plst[i][0]];
  87.         ++vecd[plst[i][1]];
  88.         if (vecs[plst[i][0]] > maxs) {
  89.             maxs = vecs[plst[i][0]];
  90.         }
  91.         if (vecd[plst[i][1]] > maxd) {
  92.             maxd = vecd[plst[i][1]];
  93.         }
  94.     }
  95.     free(vecs);
  96.     free(vecd);
  97.     return maxs > maxd ? 0 : 1;
  98. }
  99.  
  100. void process()
  101. {
  102.     short i, j, src, dest, var, flag, old = 0, ind, first, second;
  103.     unsigned int min;
  104.     chs = 0; //getoptim(); TLE :/
  105.     if (chs) {
  106.         first = 1;
  107.         second = 0;
  108.     } else {
  109.         first = 0;
  110.         second = 1;
  111.     }
  112.     qsort(pord, paths, sizeof(short), comp);
  113.     for (i = 0; i < paths; ++i) {
  114.         ind = pord[i];
  115.         src = plst[ind][first];
  116.         dest = plst[ind][second];
  117.         if (old == src) {
  118.             globd[ind] = dist[dest];
  119.             continue;
  120.         } else {
  121.             old = src;
  122.         }
  123.         for (j = 0; j <= nodes; ++j) {
  124.             viz[j] = 0;
  125.             dist[j] = inf;
  126.         }
  127.         dist[src] = 0;
  128.         var = src;
  129.         do {
  130.             viz[var] = 1;
  131.             for (j = 1; j <= list[var][0][0]; ++j) {
  132.                 if (dist[var] + list[var][j][1] < dist[list[var][j][0]]) {
  133.                     dist[list[var][j][0]] = dist[var] + list[var][j][1];
  134.                 }
  135.             }
  136.             flag = 0;
  137.             min = inf;
  138.             for (j = 1; j <= nodes; ++j) {
  139.                 if (dist[j] < min && !viz[j]) {
  140.                     min = dist[j];
  141.                     var = j;
  142.                     flag = 1;
  143.                 }
  144.             }
  145.         } while (flag);
  146.         globd[ind] = dist[dest];
  147.     }
  148.     for (i = 0; i < paths; ++i) {
  149.         printf("%u\n", globd[i]);
  150.     }
  151. }
  152.  
  153. void clean()
  154. {
  155.     short i, j;
  156.     nodes = paths = 0;
  157.     free(viz);
  158.     free(dist);
  159.     for (i = 1; i <= nodes; ++i) {
  160.         free(name[i]);
  161.         for (j = 1; j <= list[i][0][0]; ++j) {
  162.             free(list[i][j]);
  163.         }
  164.         free(list[i][0]);
  165.         free(list[i]);
  166.     }
  167.     free(name);
  168.     free(list);
  169.     for (i = 0; i < paths; ++i) {
  170.         free(plst[i]);
  171.     }
  172.     free(plst);
  173.     free(ord);
  174.     free(pord);
  175.     free(globd);
  176. }
  177.  
  178. int main()
  179. {
  180.     short tests;
  181.     //freopen("shpath.in", "rt", stdin);
  182.     for (scanf("%hd", &tests); tests; --tests) {
  183.         read();
  184.         process();
  185.         clean();
  186.     }
  187.     return 0;
  188. }
  189.  
stdin 
1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa
compilation info 
prog.c: In function ‘read’:
prog.c:43: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
prog.c:48: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
prog.c:56: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
prog.c:63: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
prog.c:70: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
prog.c:72: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
prog.c: In function ‘main’:
prog.c:182: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
stdout 
3
2
https://ideone.com/l4glD
language:
C (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!