|
|
用的SPFA算法。
 #include <stdio.h>
#include <stdlib.h>
#define MAX_N 1024
#define MAX_T 2048
  struct edge_node  {
 int idx, len;
struct edge_node *next;
 };
struct edge_node edges[MAX_T * 2], *map[MAX_N];
int N, T, D[MAX_N], queue[MAX_N], qh, qt, visited[MAX_N];
__inline void add_edge(struct edge_node *e, int from, int to, int len)
{
e->idx = to;
e->len = len;
e->next = map[from];
map[from] = e;
}
int main()
{
int i, from, to, len;
struct edge_node *e;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &T, &N);
  for (i = 0; i < T * 2; i += 2) {
scanf("%d%d%d", &from, &to, &len);
add_edge(&edges[i], from, to, len);
add_edge(&edges[i + 1], to, from, len);
 }
for (i = 1; i <= N; i++)
D[i] = 0x00ffffff;
queue[0] = N;
visited[N] = 1;
D[N] = 0;
qh = 0;
qt = 1;
while (qh != qt) {
i = queue[qh++];
qh &= _countof(queue) - 1;
visited[i] = 0;
for (e = map[i]; e; e = e->next) {
if (D[i] + e->len < D[e->idx]) {
D[e->idx] = D[i] + e->len;
if (!visited[e->idx]) {
visited[e->idx] = 1;
queue[qt++] = e->idx;
qt &= _countof(queue) - 1;
}
}
}
}
printf("%d\n", D[1]);
return 0;
}
|