這個題目很好，推薦一下。
問題來源：
武漢大學2008年校賽網絡預選賽提交方式：
http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1352
問題描述（點擊查看
具體描述）：
給定一個無向圖，給定源點和終點，找到他們之間最短奇數和偶數路徑。
（奇偶是指經過的邊的條數）。
解題思路：
Dijstra或BFS都可以。
我用Dijstra過的，關鍵地方就是對于一個點保存兩個值——到當前點的最短奇數和偶數路徑的長度，一個點到另外一點可以通過奇偶性推出來。
解題總結：
這個題目我由于當時對Dijstra理解不夠深刻，沒有寫過Distra＋優先隊列的程序，沒有做出來——其實Dijstra＋優先隊列的思想我早就知道，一直沒寫，下次不能這么懶惰了。
我目前不會C＋＋的STL，寫的程序比較冗長——開始學習STL，讓程序向簡捷發展。
一點想法：
其實可以出一道題目求從源點到終點的N種路徑，做法類似：直接取模就可以了，:)
程序代碼：
由于本題的寫法比較簡單，而且由于WOJ代碼是開放的，大家直接去把這個題目過了就可以看到各種各樣的寫法了，這里只貼我的Distrea+優先隊列標準程序（按上面方法轉換馬上就可以過），爭取很快貼個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
posted on 2008-04-01 14:47
R2 閱讀(2048)
評論(0) 編輯 收藏 引用 所屬分類:
Problem Solving 、
Standing Programs