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

            pku 2472

            2009年7月25日

            題目鏈接:PKU 2472 106 miles to Chicago

            分類:最短路變形

            題目分析與算法原型
                     其實這道題目的本質是一個“最短路徑”問題,就用Dijkastra算法即可解決,不過,需要注意的是運用時,我們不再求最小的代價而是求最大的代價,即為最大的不被逮捕的概率,所以需要對Dijkastra做一些改進,除了將最短改成最大的之外,還要將“+”改成“*” 

            Code:

             1
            #include<stdio.h>
             2#include<string.h>
             3#define min -1
             4#define len 105
             5
             6int n,m,i,j,flag[len],u;
             7double map[len][len],dis[len];
             8
             9void init()
            10{
            11    for(i=1;i<=n;i++)
            12        for(j=1;j<=n;j++)
            13        {
            14            if(i==j)map[i][j]=0;
            15            else map[i][j]=min;
            16        }

            17}

            18
            19void dij(int v0)  //此題求最大路徑
            20{
            21    for(i=1;i<=n;i++)dis[i]=map[v0][i];
            22    flag[v0]=1;
            23    
            24    for(i=1;i<n;i++)
            25    {
            26        double max=min;
            27        for(j=1;j<=n;j++)
            28            if(flag[j]==0&&dis[j]>max)
            29            {
            30                u=j;
            31                max=dis[j];
            32            }

            33        if(max==min)return ;
            34        flag[u]=1;
            35        for(j=1;j<=n;j++)
            36            if(flag[j]==0&&map[u][j]>min&&dis[u]*map[u][j]>dis[j])
            37                dis[j]=dis[u]*map[u][j];
            38    }

            39}

            40
            41int main()
            42{
            43    while(scanf("%d",&n)!=EOF&&n)
            44    {
            45        scanf("%d",&m);
            46        init();
            47        memset(flag,0,sizeof(flag));
            48        for(i=0;i<m;i++)
            49        {
            50            int a,b;
            51            double p;
            52            scanf("%d%d%lf",&a,&b,&p);
            53            if(p>map[a][b])
            54            {
            55                map[a][b]=p/100;
            56                map[b][a]=p/100;
            57            }

            58        }

            59        dij(1);
            60        printf("%.6lf percent\n",dis[n]*100);
            61    }

            62    return 0;
            63}

            64

            posted on 2009-07-25 14:50 蝸牛也Coding 閱讀(252) 評論(0)  編輯 收藏 引用

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            常用鏈接

            留言簿(8)

            隨筆檔案(78)

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲va中文字幕无码久久不卡| 国产午夜精品理论片久久影视| 国产精品青草久久久久婷婷| 91精品日韩人妻无码久久不卡| 色婷婷久久久SWAG精品| 777午夜精品久久av蜜臀| 精品欧美一区二区三区久久久 | 久久久久久极精品久久久| 思思久久好好热精品国产| 久久99精品综合国产首页| 国产99久久久国产精品~~牛| 久久久噜噜噜www成人网| 久久久午夜精品福利内容| 国产人久久人人人人爽| 精品国产乱码久久久久久呢| 久久精品夜色噜噜亚洲A∨| 久久无码高潮喷水| 久久精品久久久久观看99水蜜桃| 久久精品中文闷骚内射| 久久久久亚洲AV成人网人人网站 | 国产成年无码久久久免费| 久久99热精品| 狼狼综合久久久久综合网| 久久综合亚洲鲁鲁五月天| 久久这里只有精品久久| 国产精品丝袜久久久久久不卡| 丁香色欲久久久久久综合网| 国产成人久久精品二区三区| 久久66热人妻偷产精品9| 思思久久99热只有频精品66| 精品久久人人做人人爽综合| 久久精品草草草| 国产人久久人人人人爽| 久久99国产综合精品| 亚洲精品乱码久久久久久蜜桃图片| 少妇被又大又粗又爽毛片久久黑人| 99精品国产在热久久无毒不卡| 国产69精品久久久久9999APGF| 久久天天躁夜夜躁狠狠| 久久婷婷五月综合色奶水99啪| 久久e热在这里只有国产中文精品99 |