青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku 1122

2009年7月29日

題目鏈接:PKU 1122 FDNY to the Rescue!
  
分類:Diskastra

題目分析與算法原型
        有點郁悶,這題由于題目意思沒看仔細加上有些位置沒有理解充分,貢獻了好幾次WA,雖然只是一個Dijkastra的簡單應用,不過此題還是要細心應對的,大致做法是先將輸入的矩陣轉置一下,使得單終點最短路徑變成單源點最短路徑,然后用Dijkastra處理即可(注意題目的一些提示條件,看清楚題目意思)


Code:

  1
#include<stdio.h>
  2#include<stdlib.h>
  3#include<string.h>
  4#define max 1000000000
  5#define len 25
  6
  7int n,map[len][len],dis[len],s,adj[len],path[len],visit[len];
  8bool finish;
  9
 10struct node
 11{
 12    int dis,num;
 13}
place[len];
 14
 15void init()
 16{
 17    int i,j;
 18    for(i=1;i<=n;i++)
 19        for(j=1;j<=n;j++)
 20        {
 21            if(i==j)map[i][j]=0;
 22            else map[i][j]=max;
 23        }

 24}

 25int cmp(const void * a,const void * b)
 26{
 27    return (*(node *)a).dis > (*(node *)b).dis ? 1:-1;
 28}

 29void Dijkastra(int s)//s為源點
 30{
 31    int i,j;
 32    for(i=1;i<=n;i++)
 33    {
 34        dis[i]=map[s][i];
 35        visit[i]=0;
 36        if(i!=s&&dis[i]<max)path[i]=s;
 37        else path[i]=-1;
 38    }

 39    visit[s]=1;
 40    for(i=1;i<n;i++)
 41    {
 42        int min=max,u;
 43        for(j=1;j<=n;j++)
 44            if(visit[j]==0&&dis[j]<min)
 45            {
 46                u=j;
 47                min=dis[j];
 48            }

 49            if(min==max)return;//此語句對于非連通圖是必須的,表示當前已經不存在路徑了
 50            visit[u]=1;
 51            for(j=1;j<=n;j++)
 52                if(visit[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
 53                {
 54                    dis[j]=dis[u]+map[u][j];
 55                    path[j]=u;
 56                }

 57    }

 58}

 59int main()
 60{
 61    int i,j,pos;
 62    while(scanf("%d",&n)!=EOF)
 63    {
 64        init();
 65        finish=false;
 66        for(i=1;i<=n;i++)
 67            for(j=1;j<=n;j++)
 68            {
 69                int l;
 70                scanf("%d",&l);
 71                if(l!=-1)map[j][i]=l;
 72            }

 73            scanf("%d",&s);
 74            pos=0;
 75            char ch;
 76            memset(adj,0,sizeof(adj));
 77
 78            printf("Org\tDest\tTime\tPath\n");
 79            while(1)
 80            {
 81                ch=getchar();
 82                if(ch==10)break;
 83                while(!(ch>='0'&&ch<='9'))ch=getchar();
 84                
 85                while(ch>='0'&&ch<='9')
 86                {
 87                    adj[pos]*=10;
 88                    adj[pos]+=ch-'0';
 89                    ch=getchar();
 90                }

 91                
 92                if(adj[pos]==s)
 93                {
 94                    printf("%d\t%d\t%d\t%d\n",s,s,0,s);
 95                    adj[pos]=0;
 96                }

 97                else pos++;
 98                if(ch==10)break;
 99            }

100            Dijkastra(s);
101            for(i=0;i<pos;i++)
102            {
103                place[i].dis=dis[adj[i]];
104                place[i].num=adj[i];
105            }

106            qsort(place,pos,sizeof(place[0]),cmp);
107            
108            
109            for(i=0;i<pos;i++)
110            {
111                printf("%d\t%d\t%d\t%d\t",place[i].num,s,place[i].dis,place[i].num);
112                int kk=path[place[i].num];
113                while(1)
114                {
115                    printf("%d",kk);
116                    if(kk==s)break;
117                    else printf("\t");
118                    kk=path[kk];
119                }

120                printf("\n");
121            }

122    }

123    return 0;            
124}

posted on 2009-07-29 20:12 蝸牛也Coding 閱讀(266) 評論(0)  編輯 收藏 引用


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


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

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            老司机成人在线视频| 欧美视频日韩| 欧美.日韩.国产.一区.二区| 国产精品嫩草久久久久| 亚洲三级免费电影| 欧美ed2k| 久久综合九色综合网站| 国产一区二区三区久久 | 欧美国产视频一区二区| 国精品一区二区三区| 久久国产免费看| 亚洲桃色在线一区| 国产精品乱码久久久久久| 亚洲欧美国产日韩天堂区| 一区二区精品在线| 国产精品亚洲综合| 久久国产精品第一页| 亚洲欧美日韩成人高清在线一区| 国产精品久久国产三级国电话系列| 正在播放欧美视频| 日韩午夜电影| 国产精品国产自产拍高清av| 亚洲欧美中文另类| 欧美在线精品免播放器视频| 在线电影国产精品| 亚洲国产美女| 欧美剧在线观看| 亚洲欧美在线播放| 欧美在线在线| 99精品国产99久久久久久福利| 亚洲精品视频免费观看| 欧美午夜美女看片| 欧美在线观看一区二区三区| 久久精品成人一区二区三区蜜臀| 亚洲成色精品| 亚洲精品日韩一| 国产女人水真多18毛片18精品视频| 久久久久久久久一区二区| 久久久蜜臀国产一区二区| 亚洲毛片视频| 先锋影音一区二区三区| 亚洲国产精品999| av成人动漫| 国产一区二区三区四区在线观看| 欧美成在线视频| 国产精品v欧美精品∨日韩| 久久久久久伊人| 欧美韩日一区二区三区| 欧美一区二区三区啪啪| 欧美v国产在线一区二区三区| 亚洲一区二区三区精品视频| 久久久久9999亚洲精品| 一区二区欧美精品| 久久精品女人| 亚洲欧洲99久久| 欧美+日本+国产+在线a∨观看| 亚洲欧美日韩在线播放| 久久天天狠狠| 欧美一区二区性| 欧美区亚洲区| 噜噜爱69成人精品| 国产精品海角社区在线观看| 欧美高清在线一区二区| 国产精品综合视频| 亚洲精品美女在线观看| 在线观看成人av| 香蕉av福利精品导航| 亚洲一区二区三区国产| 欧美久久电影| 亚洲国产成人高清精品| 亚洲图片在线| 欧美美女bb生活片| 免费观看在线综合色| 国产精品视频网| 日韩亚洲国产欧美| 亚洲美女尤物影院| 模特精品在线| 麻豆精品在线播放| 国产视频久久久久| 亚洲小说欧美另类社区| 亚洲特色特黄| 欧美日韩精品综合在线| 亚洲国产专区| 亚洲精品视频免费在线观看| 麻豆av一区二区三区| 女人天堂亚洲aⅴ在线观看| 国产日韩欧美一区二区| 亚洲免费在线观看| 欧美一区二区三区在线| 国产嫩草一区二区三区在线观看| 日韩一二三在线视频播| 一本一本a久久| 欧美精品aa| 9色精品在线| 亚洲欧美制服另类日韩| 国产精品日韩| 午夜精品久久| 久热精品视频| 亚洲精品国久久99热| 欧美成年人网| 日韩午夜激情av| 午夜精品视频| 国产日韩在线一区二区三区| 欧美一区二区三区四区在线观看地址| 欧美在线观看天堂一区二区三区| 国产欧美日韩免费| 久久精品91| 亚洲电影免费在线| 亚洲无限乱码一二三四麻| 国产精品视频yy9299一区| 午夜精品久久久久久久久久久| 欧美在线播放一区二区| 亚洲成人在线免费| 欧美精品一区在线发布| 99精品视频免费全部在线| 新67194成人永久网站| 国产在线麻豆精品观看| 男女精品视频| 亚洲永久精品国产| 亚洲第一成人在线| 欧美一级二区| 亚洲黄色影片| 国产精品亚洲一区二区三区在线| 久久久久国产成人精品亚洲午夜| 亚洲国产一二三| 欧美在线视频网站| 亚洲日本中文字幕免费在线不卡| 国产精品久久久久久超碰| 久久五月天婷婷| 亚洲一区成人| 亚洲国产va精品久久久不卡综合| 亚洲欧美日韩国产成人| 亚洲高清资源| 国产伦精品一区二区三区高清| 麻豆精品视频在线观看| 亚洲香蕉视频| 亚洲黄一区二区三区| 久久免费黄色| 亚洲欧美日韩一区在线| 亚洲精品黄色| 狠狠做深爱婷婷久久综合一区| 巨乳诱惑日韩免费av| 先锋亚洲精品| 精品电影在线观看| 欧美日韩一区三区| 老色鬼精品视频在线观看播放| 亚洲免费观看在线视频| 欧美波霸影院| 久久久久久日产精品| 亚洲系列中文字幕| 亚洲国产一区二区精品专区| 国产伦精品一区二区三区视频黑人 | 蜜臀av一级做a爰片久久 | 欧美日韩国产999| 老**午夜毛片一区二区三区| 亚洲欧美国产va在线影院| 亚洲毛片播放| 亚洲日本欧美| 亚洲国产精品va在线观看黑人| 久久久久五月天| 久久久国产精品一区二区中文 | 久久久不卡网国产精品一区| 在线性视频日韩欧美| 亚洲精品国产精品国产自| 亚洲成在人线av| 在线视频成人| 亚洲电影av| 亚洲国产精品久久人人爱蜜臀| 狠狠爱综合网| 一区精品在线| 亚洲第一成人在线| 亚洲高清123| 亚洲精品日日夜夜| 日韩香蕉视频| 一区二区三区视频在线观看| 在线综合视频| 亚洲欧美乱综合| 欧美在线影院在线视频| 香蕉久久国产| 久久成人精品| 久久久蜜臀国产一区二区| 久久久女女女女999久久| 久久久久久九九九九| 麻豆av一区二区三区久久| 欧美 日韩 国产精品免费观看| 欧美成人亚洲| 亚洲精品三级| 亚洲一区二区3| 欧美在线免费视频| 老**午夜毛片一区二区三区| 欧美99在线视频观看| 欧美另类一区二区三区| 国产精品成人v| 国产亚洲一区精品| 1024精品一区二区三区| 日韩视频免费| 欧美一级一区| 欧美国产日韩在线| 亚洲特色特黄| 免费久久99精品国产自在现线|