• <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!

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

               下面是代碼:
             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)  編輯 收藏 引用

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            久久久久无码国产精品不卡| 亚洲伊人久久大香线蕉综合图片| 大伊人青草狠狠久久| 久久综合综合久久97色| 国产叼嘿久久精品久久| 久久天天躁狠狠躁夜夜2020一| 亚洲国产精品无码久久一区二区| 久久久久久久亚洲Av无码| 久久久久国色AV免费观看| 中文字幕日本人妻久久久免费| 99国内精品久久久久久久| 一本色道久久综合| 99久久精品免费看国产免费| 久久久久久综合网天天| 国产亚洲精久久久久久无码AV| 漂亮人妻被黑人久久精品| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 久久99毛片免费观看不卡| 伊人久久大香线蕉成人| 国产精品热久久无码av| 久久精品水蜜桃av综合天堂| 2021国产精品久久精品| 精品久久久久中文字幕一区| 国产产无码乱码精品久久鸭| 成人午夜精品无码区久久| 麻豆久久| 欧美久久久久久午夜精品| 久久精品成人免费国产片小草| 久久天天躁狠狠躁夜夜躁2O2O| 亚洲午夜精品久久久久久浪潮| 久久精品国产一区二区三区不卡 | 免费精品国产日韩热久久| 久久精品国产亚洲AV香蕉| 久久热这里只有精品在线观看| 无码国内精品久久人妻麻豆按摩| 99国内精品久久久久久久| Xx性欧美肥妇精品久久久久久| 青青草国产精品久久久久| 久久香蕉国产线看观看99| 国产高清美女一级a毛片久久w| 久久免费高清视频|