# Untitled

unknown
plain_text
2 years ago
1.2 kB
1
Indexable
Never
```#include<stdio.h>
#define MAX_N 100
#define NO_EDGE -1
#define oo 9999
typedef struct {
int n, m, w;
int W[MAX_N][MAX_N];
} Graph;

void init_graph(Graph *pG, int n) {
int u, v;
pG->n = n;
for(u = 1; u <= n; u++)
for(v = 1; v <= n; v++)
pG->W[u][v] = NO_EDGE;
}

void add_edge(Graph *pG, int u, int v, int w) {
pG->W[u][v] = w;
pG->W[v][u] = w;
pG->m++;
}

int mark[MAX_N];
int pi[MAX_N];
int p[MAX_N];

void MooreDijkstra(Graph *pG, int s) {
int u, v, j, it;
for(u = 1; u <= pG->n; u++) {
pi[u] = oo;
mark[u] = 0;
}
pi[s] = 0;
p[s] = -1;
for(it = 1; it < pG->n; it++) {
int min_pi = oo;
for(j = 1; j <= pG->n; j++)
if(mark[j] == 0 && pi[j] < min_pi) {
min_pi = pi[j];
u = j;
}
mark[u] = 1;
for(v = 1; v <= pG->n; v++)
if(mark[v] == 0 && pG->W[u][v] != NO_EDGE)
if(pi[v] > min_pi + pG->W[u][v]) {
pi[v] = min_pi + pG->W[u][v];
p[v] = u;
}
}
}

int main() {
Graph G;
int n, m, u, v, w, i;
scanf("%d%d", &n, &m);
init_graph(&G, n);
for(i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);