dijkstra/dijkstra-in-c.c at master · thinkphp/dijkstra · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <stdio.h>
#include <stdlib.h>
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define oo ((1LL<<31) - 1)
#define MAXN 50005

int nodes,
    edges;

typedef struct NODE {
        int y,
            cost;
        struct Node *next;
} *PNODE, NODE;

PNODE ListNodes[ MAXN ];

int distMin[ MAXN ];
char selectedNode[ MAXN ];

void ADDEdge(const int x, const int y, const int cost) {

     PNODE newNode = ( PNODE )calloc(1, sizeof( NODE ) );
           newNode->y = y;
           newNode->cost = cost;
           newNode->next = ListNodes[ x ];
           ListNodes[ x ] = newNode;
};

void readData() {

     int x,
         y,
         c;

     freopen(FIN, "r", stdin);

     scanf("%d %d", &nodes, &edges);

     for(;edges; edges--) {

         scanf("%d %d %d", &x, &y, &c);

         ADDEdge(x, y, c);
     }

     fclose( stdin );
};

void dijkstra() {

     PNODE prim = NULL,
           last = NULL,
           p;
     int i,
         curr;

     for(i = 2; i <= nodes; i++) distMin[ i ] = oo;

     distMin[ 1 ] = 0;

     selectedNode[ 1 ] = 1;

     prim = last = (PNODE)calloc(1,sizeof(NODE));

     prim->y = 1;

     prim->next = NULL;

     while( prim ) {

            curr = prim->y;

            selectedNode[ curr ] = 0;

            for(p = ListNodes[ curr ]; p; p = p->next) {

                if(distMin[ p->y ] > distMin[ curr ] + p->cost) {

                   distMin[ p->y ] = distMin[ curr ] + p->cost;

                   if(!selectedNode[ p->y ]) {

                       selectedNode[ p->y ] = 1;

                       PNODE o = (PNODE)calloc(1, sizeof(NODE));
                             o->y = p->y;
                             o->cost = p->cost;
                             o->next = NULL;
                             last->next = o;
                             last = last->next;
                   }
                }
            }

            PNODE aux = prim;
            prim = prim->next;
            free( aux );
     }
};

void writeData() {

     freopen(FOUT, "w", stdout);

     int i;
     for(i = 2; i <= nodes; i++) printf("%d ", distMin[ i ] < oo ? distMin[ i ] : 0);

     fclose( stdout );
}

int main() {

    readData();
    dijkstra();
    writeData();

 return(0);
};