• <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>
            posts - 6,comments - 4,trackbacks - 0

             

            2012年11月9日 明天就是NOIP 2012 Day1!

               再放一份代碼,其實我真的不會SPFA,集訓的時候,在國家集訓隊的論文里看到了一句話:“SPFA算法其實是Bellman-Ford算法的一個進一步優化的版本。”所以我把這個當成SPFA了,效果不錯,為了簡單起見用了STL。寫起來很像BFS的尋路,還很像DP的過程,所以很快就會理解。
               如果想用堆優化,就直接把隊列換成優先隊列就可以了。

               下面是代碼:
             1 #include <cstdio>
             2 #include <cstring>
             3 #include <queue>
             4 using namespace std;
             5 
             6 #define MAXN 10007
             7 #define INF 100000007
             8 
             9 typedef struct G_NODE
            10 {
            11     int u, v, w;
            12     struct G_NODE *next;
            13 } Gnode;
            14 
            15 int n, m, d[MAXN];
            16 Gnode *a[MAXN];
            17 
            18 void add_edge(int x, int y, int w)
            19 {
            20     Gnode *= new Gnode;
            21     p->= x;
            22     p->= y;
            23     p->= w;
            24     p->next = a[x]->next;
            25     a[x]->next = p;
            26 }
            27 
            28 bool bellman_ford(int s)
            29 {
            30     bool inq[MAXN];
            31     int cnt[MAXN];
            32     queue<int> q;
            33     Gnode *p;
            34 
            35     memset(inq, falsesizeof(inq));
            36     memset(cnt, 0sizeof(cnt));
            37     for (int i = 1; i <= n; ++i)
            38         d[i] = (i == s ? 0 : INF);
            39     q.push(s);
            40     inq[s] = true;
            41     ++cnt[s];
            42     
            43     while (!q.empty())
            44     {
            45         int i = q.front();
            46         q.pop();
            47         inq[i] = false;
            48         for (p = a[i]->next; p; p = p->next)
            49         {
            50             int j = p->v;
            51             if (d[i] + p->< d[j])
            52             {
            53                 d[j] = d[i] + p->w;
            54                 if (!inq[j])
            55                 {
            56                     q.push(j);
            57                     inq[j] = true;
            58                     ++cnt[j];
            59                     if (cnt[j] > n)
            60                         return false;
            61                 }
            62             }
            63         }
            64     }
            65     return true;
            66 }
            67 
            68 int main()
            69 {
            70     freopen("g.in""r", stdin);
            71     freopen("g.out""w", stdout);
            72 
            73     scanf("%d %d"&n, &m);
            74     for (int i = 1; i <= n; ++i)
            75     {
            76         a[i] = new Gnode;
            77         a[i]->next = NULL;
            78     }
            79     for (int i = 1; i <= m; ++i)
            80     {
            81         int x, y, w;
            82         scanf("%d %d %d"&x, &y, &w);
            83         add_edge(x, y, w);
            84         add_edge(y, x, w);
            85     }
            86     if (bellman_ford(1))
            87     {
            88         for (int i = 1; i < n; ++i)
            89             printf("%d ", d[i]);
            90         printf("%d", d[n]);
            91         putchar('\n');
            92     }
            93     else printf("Failded\n");

            94 
            95     return 0;
            96 }

             

            posted on 2012-11-09 13:29 molasses 閱讀(1228) 評論(0)  編輯 收藏 引用
            久久久久亚洲精品男人的天堂| 亚洲中文字幕无码一久久区| 女人香蕉久久**毛片精品| 欧美伊香蕉久久综合类网站| 久久五月精品中文字幕| 亚洲午夜无码久久久久小说| 亚洲午夜无码久久久久| 一本一道久久精品综合| 久久午夜夜伦鲁鲁片免费无码影视 | 一本一道久久综合狠狠老| 国产成人久久AV免费| 久久久久久无码国产精品中文字幕| 亚洲国产精品成人久久蜜臀| 久久国产精品77777| 亚洲欧美另类日本久久国产真实乱对白 | 亚洲&#228;v永久无码精品天堂久久| 漂亮人妻被中出中文字幕久久| 97久久久久人妻精品专区| 亚洲欧美久久久久9999| 久久黄色视频| 91久久精品视频| 久久A级毛片免费观看| 伊人久久综合无码成人网| 久久久久亚洲AV成人网| 久久久精品一区二区三区| 精品久久久久久久久午夜福利| 模特私拍国产精品久久| 日韩精品无码久久一区二区三| 国产午夜免费高清久久影院| 国产偷久久久精品专区| 久久综合鬼色88久久精品综合自在自线噜噜| 精品久久久久久中文字幕| 精品久久久久久久无码| 国产成人无码久久久精品一| 国产精品久久久久jk制服| 午夜久久久久久禁播电影| 亚洲乱码中文字幕久久孕妇黑人| 久久久久人妻一区二区三区| 久久久久久午夜精品| 99精品久久精品一区二区| 久久精品中文字幕无码绿巨人|