這個(gè)題目很好，推薦一下。
問題來源：
武漢大學(xué)2008年校賽網(wǎng)絡(luò)預(yù)選賽提交方式：
http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1352
問題描述（點(diǎn)擊查看
具體描述）：
給定一個(gè)無向圖，給定源點(diǎn)和終點(diǎn)，找到他們之間最短奇數(shù)和偶數(shù)路徑。
（奇偶是指經(jīng)過的邊的條數(shù)）。
解題思路：
Dijstra或BFS都可以。
我用Dijstra過的，關(guān)鍵地方就是對(duì)于一個(gè)點(diǎn)保存兩個(gè)值——到當(dāng)前點(diǎn)的最短奇數(shù)和偶數(shù)路徑的長(zhǎng)度，一個(gè)點(diǎn)到另外一點(diǎn)可以通過奇偶性推出來。
解題總結(jié)：
這個(gè)題目我由于當(dāng)時(shí)對(duì)Dijstra理解不夠深刻，沒有寫過Distra＋優(yōu)先隊(duì)列的程序，沒有做出來——其實(shí)Dijstra＋優(yōu)先隊(duì)列的思想我早就知道，一直沒寫，下次不能這么懶惰了。
我目前不會(huì)C＋＋的STL，寫的程序比較冗長(zhǎng)——開始學(xué)習(xí)STL，讓程序向簡(jiǎn)捷發(fā)展。
一點(diǎn)想法：
其實(shí)可以出一道題目求從源點(diǎn)到終點(diǎn)的N種路徑，做法類似：直接取模就可以了，:)
程序代碼：
由于本題的寫法比較簡(jiǎn)單，而且由于WOJ代碼是開放的，大家直接去把這個(gè)題目過了就可以看到各種各樣的寫法了，這里只貼我的Distrea+優(yōu)先隊(duì)列標(biāo)準(zhǔn)程序（按上面方法轉(zhuǎn)換馬上就可以過），爭(zhēng)取很快貼個(gè)C++版的??！
1 #include <iostream>
2 using namespace std;
3
4 #define N 2002
5
6 const int large_number = 200000000; //???
7
8 typedef struct t_edge {
9 int dis;
10 int id;
11 t_edge *next;
12 };
13
14 typedef struct t_heap {
15 int data[ N ];
16 int size;
17 };
18
19 typedef struct t_node {
20 int dis;
21 int pos;
22 };
23
24 t_edge *g[ N ];
25 t_heap heap;
26 t_node node[ N ];
27 int n, m, s, t;
28
29 inline void insert(int u, int v, int dis) {
30 t_edge *p;
31 p = new t_edge;
32 p->id = v, p->dis = dis, p->next = g[u];
33 g[u] = p;
34 }
35
36 void del(t_edge *p) {
37 if (p == NULL) return ;
38 del(p->next);
39 delete p;
40 }
41
42 void init() {
43 for (int i = 0; i < n; i ++) g[i] = NULL;///
44 int u, v, dis;
45 for (int i = 1; i <= m; i ++) {
46 scanf("%d %d %d", &u, &v, &dis);
47 insert(u, v, dis);
48 }
49 }
50
51 void SiftDown(int i) {
52 int min = i, lc = i*2, rc = lc+1;
53 if (lc <= heap.size && node[ heap.data[min] ].dis > node[ heap.data[lc] ].dis) {
54 min = lc;
55 }
56 if (rc <= heap.size && node[ heap.data[min] ].dis > node[ heap.data[rc] ].dis) {
57 min = rc;
58 }
59 if (min != i) {
60 int tmp = heap.data[ min ];
61 heap.data[ min ] = heap.data[i], heap.data[ i ] = tmp;
62 node[ heap.data[min] ].pos = min, node[ heap.data[i] ].pos = i;
63 SiftDown(min);
64 }
65 }
66
67 void SiftUp(int i) {
68 int father;
69 while (i != 1)
70 {
71 father = i/2;
72 if (node[ heap.data[father] ].dis > node[ heap.data[i] ].dis) {
73 int tmp = heap.data[ father ];
74 heap.data[father] = heap.data[i], heap.data[i] = tmp;
75 node[ heap.data[father] ].pos = father, node[ heap.data[i] ].pos = i;
76 }
77 else break;
78 i = father;
79 }
80 }
81
82 int extra_min() {
83 if (heap.size == 0) return -1;
84 int re = heap.data[1];
85 heap.data[1] = heap.data[ heap.size ], heap.size --;
86 node[ heap.data[1] ].pos = 1;
87 SiftDown(1);
88 return re;
89 }
90
91 void build_queue() {
92 for (int i = 0; i < n; i ++) {
93 heap.data[i+1] = i;
94 node[i].pos = i+1;
95 node[i].dis = large_number;
96 }
97 heap.size = n;
98 node[s].dis = 0;
99 node[s].pos = 1, heap.data[1] = s;
100 heap.data[s+1] = 0, node[0].pos = s+1;
101 }
102
103 void Dijstra() {
104 build_queue();
105 int cur, tmp;
106 t_edge *p;
107 while (true) {
108 cur = extra_min();
109 if (cur < 0) break;
110 p = g[ cur ];
111 while (p != NULL) {
112 tmp = node[cur].dis + p->dis;
113 if (node[ p->id ].dis > tmp) {
114 node[ p->id ].dis = tmp;
115 SiftUp(node[ p->id ].pos);
116 }
117 p = p->next;
118 }
119 }
120 }
121
122 void output()
123 {
124 for (int i = 0; i < n; i ++)
125 {
126 if (node[i].dis < large_number) printf("dis[ %d ] = %d\n", i, node[i].dis);
127 else printf("node %d can\'t be reached!", i);
128 }
129 }
130
131 int main()
132 {
133 while (scanf("%d %d %d %d", &n, &m, &s, &t) != EOF)
134 {
135 init();
136 Dijstra();
137 output();
138 }
139 return 0;
140 }
141