• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅信:勤能補拙

            PKU 1724 ROADS

            問題:
            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, 0sizeof(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(100);
            57     if(min_len == INF)
            58         printf("-1\n");
            59     else
            60         printf("%d\n", min_len);
            61 }


            posted on 2010-08-02 15:10 simplyzhao 閱讀(217) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導航

            <2011年10月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲AⅤ优女AV综合久久久| 思思久久99热免费精品6| 国产精品久久久久国产A级| 99久久精品国产高清一区二区| 国产精品99久久99久久久| 久久久噜噜噜久久中文字幕色伊伊| 伊人久久大香线蕉成人| 99久久精品日本一区二区免费| 国产激情久久久久影院老熟女| 久久受www免费人成_看片中文| 国产精品久久久久久影院| 青青青青久久精品国产h久久精品五福影院1421 | 亚洲国产精品久久电影欧美| 99久久国产综合精品麻豆| 国内精品伊人久久久影院 | 精品久久久久久无码免费| 无码人妻少妇久久中文字幕蜜桃| 色婷婷狠狠久久综合五月| 国产精品久久永久免费| 无码精品久久久久久人妻中字| 久久久受www免费人成| 国内精品伊人久久久久| 久久精品水蜜桃av综合天堂 | 久久亚洲国产欧洲精品一| 少妇久久久久久久久久| 久久久久久精品免费看SSS| 久久久久亚洲爆乳少妇无| 亚洲综合久久综合激情久久| 国产成人久久精品区一区二区| 午夜精品久久久久久99热| 武侠古典久久婷婷狼人伊人| 欧美大战日韩91综合一区婷婷久久青草 | 综合网日日天干夜夜久久| 色狠狠久久综合网| 国内精品伊人久久久久妇| 久久经典免费视频| 77777亚洲午夜久久多喷| 亚洲中文久久精品无码ww16| 久久精品国产亚洲精品2020| 久久99精品久久只有精品| 久久精品国产99国产精偷|