問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1724思路:
有點與PKU 3256類似的題
第一個想法就是深搜
第一遍代碼(WA):
對于discuss里的測試數據該代碼是沒有問題的，可結果還是WA...
1 #define MAX_CITIES 101
2 #define INF 100000
3 int road[MAX_CITIES][MAX_CITIES];
4 int length[MAX_CITIES][MAX_CITIES];
5 int toll[MAX_CITIES][MAX_CITIES];
6 int visited[MAX_CITIES];
7 int k, n, r;
8 int min_len;
9
10 void
11 dfs(int city, int cur_len, int cur_toll)
12 {
14 int i;
15 visited[city] = 1;
16 if(cur_len>=min_len || cur_toll>k) {
17 visited[city] = 0;
18 return;
19 }
20 if(city == n) {
21 min_len = cur_len;
22 visited[city] = 0;
23 return;
24 }
25 for(i=1; i<=n; i++) {
26 if(road[city][i] && !visited[i])
27 dfs(i, cur_len+length[city][i], cur_toll+toll[city][i]);
28 }
29 visited[city] = 0;
30 }
繼續翻查discuss里，發現有人說兩點之間可能有多條路徑...
然后看到其他人代碼是使用鏈表來保存所有的路徑，所以修改后的AC代碼如下:
1 #define MAX_CITIES 101
2 #define INF 100000
3 struct Node {
4 int dest;
5 int len;
6 int toll;
7 struct Node *next;
8 };
9 struct Node roads[MAX_CITIES];
10 struct Node backup[MAX_CITIES*MAX_CITIES];
11 int visited[MAX_CITIES];
12 int k, n, r;
13 int min_len;
14
15 void
16 dfs(int c, int cur_len, int cur_toll)
17 {
18 int i;
19 struct Node *node;
20 if(cur_len>=min_len || cur_toll>k)
21 return;
22 if(c == n) {
23 min_len = cur_len;
24 return;
25 }
26 for(node=roads[c].next; node!=NULL; node=node->next) {
27 if(!visited[node->dest]) {
28 visited[node->dest] = 1;
29 dfs(node->dest, cur_len+node->len, cur_toll+node->toll);
30 visited[node->dest] = 0;
31 }
32 }
33 }
34
35 int
36 main(int argc, char **argv)
37 {
38 int i, s, d, l, t, cnt=0;
39 memset(visited, 0, sizeof(visited));
40 scanf("%d", &k);
41 scanf("%d", &n);
42 scanf("%d", &r);
43 for(i=1; i<=n; i++)
44 roads[i].next = NULL;
45 for(i=0; i<r; i++) {
46 scanf("%d %d %d %d", &s, &d, &l, &t);
47 backup[cnt].dest = d;
48 backup[cnt].len = l;
49 backup[cnt].toll = t;
50 backup[cnt].next = roads[s].next;
51 roads[s].next = backup+cnt;
52 ++cnt;
53 }
54 min_len = INF;
55 visited[1] = 1;
56 dfs(1, 0, 0);
57 if(min_len == INF)
58 printf("-1\n");
59 else
60 printf("%d\n", min_len);
61 }