• <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 閱讀(1238) 評論(0)  編輯 收藏 引用
            国产毛片久久久久久国产毛片 | 99久久无码一区人妻| 亚洲AV日韩精品久久久久久久| 久久婷婷五月综合成人D啪| 日产精品久久久久久久| 无码人妻精品一区二区三区久久久| 亚洲色大成网站www久久九| 曰曰摸天天摸人人看久久久| 久久久久久久久久免免费精品| 国产精品99久久久精品无码| 久久九九有精品国产23百花影院| 日韩十八禁一区二区久久| 久久精品国产亚洲综合色| 日韩欧美亚洲综合久久| 国产精品久久久久久久久| 一级做a爰片久久毛片看看| 麻豆精品久久久一区二区| 久久只有这里有精品4| 99久久精品国产综合一区 | 久久91亚洲人成电影网站| 国产精品成人99久久久久91gav| 国内精品久久久久影院薰衣草| 国产日韩久久久精品影院首页| 国产成人精品久久| 日日狠狠久久偷偷色综合免费| 2021少妇久久久久久久久久| 久久成人小视频| 色婷婷综合久久久久中文字幕 | 久久国产精品无码网站| 久久精品国产亚洲AV无码娇色| 伊人久久大香线蕉综合热线| 香蕉久久一区二区不卡无毒影院| 久久精品九九亚洲精品| 狠狠色丁香久久婷婷综合_中| 久久久久久一区国产精品| 91精品国产色综久久| AV色综合久久天堂AV色综合在| 久久国产精品国产自线拍免费| 久久精品人人做人人妻人人玩| 久久精品国产清自在天天线| 中文字幕精品久久|