問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3411思路:
做過幾道類似的題，DFS
不過，這一道有點(diǎn)特殊，每條邊以及每個(gè)點(diǎn)的訪問次數(shù)并非只有一次，為了能夠預(yù)付款，需要重復(fù)訪問某個(gè)點(diǎn)或者邊
這樣出現(xiàn)的一個(gè)問題就是搜索何時(shí)結(jié)束？這里參考了網(wǎng)上的代碼: 重復(fù)訪問的原因是為了能夠預(yù)先到達(dá)某個(gè)城市，而城市的總個(gè)數(shù)為N，也就是說，每個(gè)點(diǎn)的重復(fù)訪問次數(shù)不需要超過N
另外，由于每兩個(gè)點(diǎn)之間可能存在多條路徑，因此不能使用鄰接矩陣，而需要鄰接表
代碼
1 int N, m;
2 int min;
3 int mark[MAX_LEN];
4 struct Node {
5 int dest;
6 int adv;
7 int p, r;
8 struct Node *next;
9 };
10 struct Node *roads[MAX_LEN];
11 struct Node save[MAX_LEN];
12
13 void
14 init()
15 {
16 int i, a, b, c, p, r, cnt = 0;
17 min = INF;
18 memset(mark, 0, sizeof(mark));
19 memset(roads, 0, sizeof(roads));
20 for(i=0; i<m; i++) {
21 scanf("%d %d %d %d %d", &a, &b, &c, &p, &r);
22 save[cnt].dest = b;
23 save[cnt].adv = c;
24 save[cnt].p = p;
25 save[cnt].r = r;
26 save[cnt].next = roads[a];
27 roads[a] = save+cnt;
28 ++cnt;
29 }
30 }