这个题目很好，推荐一下。
问题来源：
武汉大学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 阅读(2029)
评论(0) 编辑 收藏 引用 所属分类:
Problem Solving 、
Standing Programs