題目鏈接：http://poj.org/problem?id=2387 一道簡簡單單的最短路的題，鑒于我對于spfa比較熟悉，就寫了個spfa，這兩天果斷的要熟悉dijstra以及spfa的各種優化。 這道題開始，圖論入門基礎也就開始，反正都是刷入門基礎，而且假期也就這么點兒時間，就不必分什么時期和專項了，一樣一樣的攻下去就行。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 #include <queue>
8 using namespace std;
9 #define N 10010
10 #define M 20010
11 int first[N], n, m, x, y, z, tot;
12 long g[N];
13 bool f[N];
14 struct edge{
15 int u, v, w, next;
16 }e[M];
17 queue<int> Q;
18 void init(){
19 for (int i = 0; i <= n; i++) g[i] = (1 << 30 - 1);
20 memset(f, 0, sizeof(f));
21 tot = 0; memset(first, 0, sizeof(first));
22 }
23 void add(int x, int y, int z){
24 tot++;
25 e[tot].u = x; e[tot].v = y; e[tot].w = z; e[tot].next = first[x]; first[x] = tot;
26 tot++;
27 e[tot].u = y; e[tot].v = x; e[tot].w = z; e[tot].next = first[y]; first[y] = tot;
28 }
29 void spfa(int st, int en){
30 f[st] = 1; Q.push(st); g[st] = 0;
31 while (!Q.empty()){
32 int now = Q.front();
33 f[now] = 0;
34 int i = first[now];
35 Q.pop();
36 while (i > 0){
37 if (g[e[i].v] > g[now] + e[i].w){
38 g[e[i].v] = g[now] + e[i].w;
39 if (!f[e[i].v]){
40 f[e[i].v] = 1;
41 Q.push(e[i].v);
42 }
43 }
44 i = e[i].next;
45 }
46 }
47 }
48 int main(){
49 while (~scanf("%d%d", &m, &n)){
50 init();
51 while (m--){
52 scanf("%d%d%d", &x, &y, &z);
53 add(x, y, z);
54 }
55 spfa(n, 1);
56 printf("%ld\n", g[1]);
57 }
58 return 0;
59 }
60
|