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

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>
            欧美在线日韩精品| 亚洲国产导航| 在线日韩中文字幕| 国内不卡一区二区三区| 狠狠爱www人成狠狠爱综合网| 韩日精品视频| 亚洲国产日韩一区| 日韩亚洲视频| 欧美一级一区| 欧美jizz19性欧美| 91久久香蕉国产日韩欧美9色| 亚洲国产欧美日韩另类综合| 99在线|亚洲一区二区| 亚洲在线免费| 麻豆国产精品777777在线 | 亚洲毛片在线免费观看| 一区二区三区国产| 久久九九国产| 欧美精品大片| 国产亚洲精品高潮| 99热免费精品| 久久这里有精品视频| 亚洲国产三级| 久久久噜噜噜久久人人看| 亚洲高清在线观看| 亚洲专区在线| 女女同性女同一区二区三区91| 欧美日产国产成人免费图片| 国产视频久久| 亚洲视频一区在线| 欧美激情国产精品| 亚洲综合第一页| 欧美精品aa| 在线观看一区欧美| 久久国产日本精品| 99av国产精品欲麻豆| 久久综合久久综合久久综合| 国产精品最新自拍| 亚洲午夜精品网| 亚洲国产另类精品专区| 久久精品一区| 国产一区三区三区| 性感少妇一区| 一区二区三区欧美在线| 欧美激情五月| 亚洲精品一区二区三区99| 久久一区二区三区四区五区| 亚洲欧美国产另类| 国产精品你懂的| 亚洲一区二区三区乱码aⅴ| 亚洲黄色成人网| 欧美gay视频| 亚洲国产日韩综合一区| 久久伊人一区二区| 欧美一区二区在线观看| 国产欧美一区视频| 欧美一区二区在线视频| 一区二区三区久久网| 欧美日韩综合| 亚洲影院色在线观看免费| 99综合电影在线视频| 欧美日韩一区二区三区在线| 在线视频你懂得一区| 亚洲免费不卡| 欧美午夜电影在线| 午夜在线精品偷拍| 亚洲欧美另类国产| 国产欧美一区二区精品仙草咪| 亚洲欧美精品一区| 亚洲免费小视频| 国产主播一区二区| 免费观看不卡av| 欧美 日韩 国产在线| 一区二区三区国产精华| 亚洲乱码国产乱码精品精天堂| 欧美日韩国内| 欧美影视一区| 蜜桃伊人久久| 亚洲免费在线| 久久深夜福利免费观看| 亚洲福利一区| 日韩视频中文字幕| 国产日韩三区| 在线免费一区三区| 亚洲欧洲精品一区二区| 91久久在线观看| 国产精品美女久久久久久久 | 国产欧美视频在线观看| 久久伊人精品天天| 欧美日韩福利视频| 久久成人精品无人区| 久久夜色精品一区| 中文av一区特黄| 久久精品国产96久久久香蕉| 亚洲片国产一区一级在线观看| 一本色道**综合亚洲精品蜜桃冫| 国产精品免费网站在线观看| 蜜桃av久久久亚洲精品| 欧美日韩亚洲一区二区三区在线 | 久久蜜桃精品| 欧美日韩在线免费| 久久精品国产综合精品| 欧美精品在线视频| 久久全国免费视频| 欧美视频日韩| 欧美激情视频给我| 国产亚洲精品久久久久久| 亚洲精品久久久一区二区三区| 国产欧美一区二区三区在线看蜜臀 | 国产一区二区高清视频| 亚洲欧洲一二三| 黄色av日韩| 亚洲欧美春色| 亚洲欧美日韩在线播放| 欧美jizzhd精品欧美巨大免费| 欧美一区国产在线| 国产精品扒开腿爽爽爽视频| 亚洲第一天堂无码专区| 黄色av一区| 久久精品国产第一区二区三区| 亚洲免费中文| 国产精品a级| 一本高清dvd不卡在线观看| 亚洲美女在线国产| 美女在线一区二区| 牛牛国产精品| 亚洲国产精品www| 久久香蕉国产线看观看av| 久久久久9999亚洲精品| 国产欧美一区二区精品忘忧草| 亚洲午夜精品久久久久久app| 一片黄亚洲嫩模| 欧美久久综合| 亚洲卡通欧美制服中文| 99re热这里只有精品视频| 欧美激情bt| 亚洲日本免费电影| 99视频精品全部免费在线| 欧美成人精品一区二区| 欧美激情影音先锋| 亚洲裸体视频| 欧美视频精品在线| 亚洲一区二区成人| 久久精品国亚洲| 久久久久久久久久久一区 | 亚洲欧美日韩精品| 国产精品v欧美精品∨日韩| 夜夜嗨av一区二区三区网站四季av| 夜夜嗨av一区二区三区网页| 欧美精品免费看| 一区二区三区国产盗摄| 久久av一区| 在线不卡中文字幕| 欧美国产先锋| 亚洲天堂成人| 久久天堂国产精品| 亚洲欧洲精品一区二区三区 | 亚洲国产经典视频| 欧美精品色综合| 亚洲天堂av高清| 麻豆精品精品国产自在97香蕉| 在线播放日韩欧美| 欧美美女福利视频| 亚洲一区欧美二区| 免费看的黄色欧美网站| 在线亚洲一区| 国产综合自拍| 欧美日韩成人一区二区| 午夜精品亚洲| 亚洲福利专区| 欧美亚洲色图校园春色| 亚洲高清在线视频| 国产精品www.| 欧美h视频在线| 午夜精品久久久久久久久| 亚洲第一在线| 久久精品亚洲热| 国产精品99久久不卡二区| 一区二区在线视频| 国产精品高潮在线| 蜜乳av另类精品一区二区| 亚洲一区二区综合| 亚洲国产成人av在线| 欧美专区第一页| 国产精品99久久久久久久vr| 国内精品视频一区| 国产精品久久久久久久久久久久久久 | 亚洲视频在线二区| 免费不卡中文字幕视频| 亚洲欧美激情在线视频| 亚洲精品网站在线播放gif| 国产日韩在线一区| 欧美三级中文字幕在线观看| 久久人人超碰| 欧美一区二区在线播放| 亚洲中无吗在线| 一区二区三区四区五区精品| 亚洲人成网站999久久久综合| 米奇777在线欧美播放| 久久午夜精品|