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

pku 1847

2009年7月24日

題目鏈接:PKU 1847 Tram

分類(lèi):最短路

題目分析與算法原型
         將需要搬動(dòng)的開(kāi)關(guān)的節(jié)點(diǎn)的權(quán)值設(shè)為1,不需要搬動(dòng)的開(kāi)關(guān)設(shè)為0,不可達(dá)的設(shè)為一個(gè)充分大的數(shù),這樣一來(lái),此題就轉(zhuǎn)換為最短路徑問(wèn)題了,3種方法(Dijkastra,Floyd以及Bellman-Ford)都可以解決

Code1: (Floyd)

 1
#include<stdio.h>
 2#define Len 105
 3#define max 99999999
 4
 5int a[Len][Len],i,j,k,n,A,B,t;
 6
 7void init()
 8{
 9    for(i=1;i<=n;i++)
10        for(j=1;j<=n;j++)
11        {
12            if(i==j)a[i][j]=0;
13            else a[i][j]=max;
14        }

15}

16int main()
17{
18    scanf("%d%d%d",&n,&A,&B);
19    init();
20    for(i=1;i<=n;i++)
21    {
22        scanf("%d",&k);
23        for(j=1;j<=k;j++)
24        {
25            scanf("%d",&t);
26            if(j==1)a[i][t]=0;
27            else a[i][t]=1;
28        }

29    }

30    for(k=1;k<=n;k++)
31        for(i=1;i<=n;i++)
32            for(j=1;j<=n;j++)
33                if(a[i][k]+a[k][j]<a[i][j])a[i][j]=a[i][k]+a[k][j];
34    
35    if(a[A][B]==max)printf("-1\n");
36    else printf("%d\n",a[A][B]);
37    return 0;
38}

39
40
 Code2:    (Dijkastra)
 
 1
#include<stdio.h>
 2#include<string.h>
 3#define Len 105
 4#define max 99999999
 5int a[Len][Len],i,j,k,n,A,B,t,flag[Len],dis[Len],min,u;
 6void init()
 7{
 8    for(i=1;i<=n;i++)
 9        for(j=1;j<=n;j++)
10        {
11            if(i==j)a[i][j]=0;
12            else a[i][j]=max;
13        }

14}

15void Dij()
16{
17    for(i=1;i<=n;i++)dis[i]=a[A][i];
18    flag[A]=1;
19    for(i=1;i<n;i++)
20    {
21        min=max;
22        for(j=1;j<=n;j++)
23            if(flag[j]==0&&dis[j]<min)
24            {
25                u=j;
26                min=dis[j];
27            }

28            if(min==max)return;
29
30            flag[u]=1;
31            for(j=1;j<=n;j++)
32                if(flag[j]==0&&a[u][j]<max&&dis[u]+a[u][j]<dis[j])
33                    dis[j]=dis[u]+a[u][j];
34    }

35}

36int main()
37{
38    scanf("%d%d%d",&n,&A,&B);
39    init();
40    memset(flag,0,sizeof(flag));
41    for(i=1;i<=n;i++)
42    {
43        scanf("%d",&k);
44        for(j=1;j<=k;j++)
45        {
46            scanf("%d",&t);
47            if(j==1)a[i][t]=0;
48            else a[i][t]=1;
49        }

50    }

51    Dij();
52    if(dis[B]==max)printf("-1\n");
53    else printf("%d\n",dis[B]);
54    return 0;
55}

56
57
Code3:(Bellman-Ford) 

 1
#include<stdio.h>
 2#define Len 105
 3#define max 99999999
 4
 5int a[Len][Len],k,n,A,B,t,dis[Len];
 6
 7void init()
 8{
 9    int i,j;
10    for(i=1;i<=n;i++)
11        for(j=1;j<=n;j++)
12        {
13            if(i==j)a[i][j]=0;
14            else a[i][j]=max;
15        }

16}

17
18void bellman_ford()
19{
20    int queue[Len*100]={0},pos=0,fp=0,i;
21    queue[pos++]=A;
22    queue[pos++]=n+1;
23    for(i=1;i<=n;i++)dis[i]=max;
24    dis[A]=0;
25    int N=1;
26    while(queue[fp])
27    {
28        int u;
29        while((u=queue[fp++])==n+1)
30        {
31            if(N++>n+1)return ;
32            queue[pos++]=n+1;
33        }

34        for(i=1;i<=n;i++)
35        {
36            if(i!=u&&a[u][i] < max)
37            {
38                if(dis[i]>dis[u]+a[u][i])
39                {
40                    dis[i]=dis[u]+a[u][i];
41                    queue[pos++]=i;
42                }

43            }

44        }

45    }

46}

47
48int main()
49{
50    scanf("%d%d%d",&n,&A,&B);
51    init();
52    int i,j;
53    for(i=1;i<=n;i++)
54    {
55        scanf("%d",&k);
56        for(j=1;j<=k;j++)
57        {
58            scanf("%d",&t);
59            if(j==1)a[i][t]=0;
60            else a[i][t]=1;
61        }

62    }

63    bellman_ford();
64    if(dis[B]==max)printf("-1\n");
65    else printf("%d\n",dis[B]);
66    return 0;
67}

68
Code4:(Bellman-Ford)

 1
#include<stdio.h>
 2#define Len 105
 3#define max 99999999
 4
 5int a[Len][Len],i,j,k,n,A,B,t,dis[Len];
 6
 7void init()
 8{
 9    for(i=1;i<=n;i++)
10        for(j=1;j<=n;j++)
11        {
12            if(i==j)a[i][j]=0;
13            else a[i][j]=max;
14        }

15}

16
17void bellman_ford()
18{
19    int i,j,k;
20    for(i=1;i<=n;i++)dis[i]=max;
21    dis[A]=0;
22    for(i=1;i<n;i++)
23    {
24        for(j=1;j<=n;j++)
25            for(k=1;k<=n;k++)
26            {
27                if(j==k)continue;
28                if(dis[k]>dis[j]+a[j][k])
29                    dis[k]=dis[j]+a[j][k];
30            }

31    }

32}

33
34int main()
35{
36    scanf("%d%d%d",&n,&A,&B);
37    init();
38    for(i=1;i<=n;i++)
39    {
40        scanf("%d",&k);
41        for(j=1;j<=k;j++)
42        {
43            scanf("%d",&t);
44            if(j==1)a[i][t]=0;
45            else a[i][t]=1;
46        }

47    }

48    bellman_ford();
49    if(dis[B]==max)printf("-1\n");
50    else printf("%d\n",dis[B]);
51    return 0;
52}

53
54
55

posted on 2009-07-24 19:07 蝸牛也Coding 閱讀(322) 評(píng)論(2)  編輯 收藏 引用

評(píng)論

# re: pku 1847 2009-09-10 18:02 Johnnx

if(j==1)a[i][t]=0;
你代碼里的這一句是什么意思,我不太明白?但卻是必須的。能給我解釋一下嗎  回復(fù)  更多評(píng)論   

# re: pku 1847 2009-09-11 01:37 蝸牛也Coding

Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.
注意題目中的這句話  回復(fù)  更多評(píng)論   


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


<2009年9月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品视频久久一区| 欧美激情视频在线播放 | 免费看亚洲片| 一区二区精品在线| 亚洲福利免费| 国产一区白浆| 欧美激情视频免费观看| 亚洲精品一区久久久久久| 久久夜色精品一区| 久久久精品一区| 久久久久99| 久久综合久色欧美综合狠狠| 西西裸体人体做爰大胆久久久| 亚洲午夜精品福利| 亚洲午夜一二三区视频| 国产精品99久久久久久www| 日韩视频在线观看免费| 国产精品一区二区黑丝| 欧美凹凸一区二区三区视频| 欧美一区二区三区视频免费播放| 欧美成人有码| 亚洲高清中文字幕| 欧美成人免费全部| 亚洲国产天堂久久国产91| 好吊日精品视频| 欧美激情第二页| 欧美国产乱视频| 欧美日韩国产一区二区三区地区 | 午夜精品成人在线| 亚洲综合首页| 亚洲综合色婷婷| 久久精品国产一区二区三区免费看| 欧美一区三区二区在线观看| 欧美在线不卡视频| 免费看的黄色欧美网站| 欧美午夜精品久久久久久孕妇| 国产精品成av人在线视午夜片 | 欧美日本国产视频| 欧美三级午夜理伦三级中文幕| 国产精品日韩精品欧美在线 | 国产日韩欧美亚洲一区| 欧美午夜一区二区三区免费大片 | 国产精品久久久久久久午夜| 国产日韩欧美在线看| 精品51国产黑色丝袜高跟鞋| 亚洲精品美女久久久久| 亚洲欧美激情在线视频| 免费观看成人| 亚洲香蕉伊综合在人在线视看| 久久精精品视频| 欧美日韩亚洲综合在线| 在线观看91精品国产麻豆| 亚洲一区二区3| 欧美韩日一区| 欧美一区二区三区免费大片| 欧美精品aa| 韩日视频一区| 欧美亚洲在线播放| 亚洲日本va在线观看| 先锋影音久久久| 欧美午夜精品理论片a级大开眼界| 精久久久久久| 最近看过的日韩成人| 久久欧美肥婆一二区| 99精品免费| 欧美成人情趣视频| 国产精品黄视频| 国产精品99久久久久久白浆小说| 欧美福利视频一区| 久久成人免费| 国产精品一区二区在线观看不卡| 99国产精品99久久久久久粉嫩| 韩国av一区| 亚洲欧美日韩精品| 亚洲国产欧美在线| 亚洲午夜一区| 先锋影音久久| 亚洲高清色综合| 午夜精品三级视频福利| 久久免费少妇高潮久久精品99| 国产精品欧美日韩久久| 在线视频你懂得一区| 亚洲欧美日韩国产中文| 亚洲美女啪啪| 欧美黄污视频| 精品成人一区二区三区| 亚洲中字在线| 91久久精品国产| 久久精品在线观看| 欧美午夜一区二区三区免费大片| 艳女tv在线观看国产一区| 久久国产福利国产秒拍| 亚洲影院色在线观看免费| 国产精品盗摄久久久| 亚洲在线一区| 久久精品中文| 亚洲日本欧美| 日韩视频在线观看免费| 国产精品久久久久久一区二区三区| 亚洲一区在线视频| 午夜在线视频观看日韩17c| 国产自产在线视频一区| 欧美成人精品一区二区| 欧美巨乳在线| 久久国产精品久久精品国产| 久久久伊人欧美| 一本色道久久综合亚洲精品不| 日韩一区二区福利| 国产视频一区免费看| 欧美成人影音| 国产精品欧美经典| 老司机免费视频一区二区| 欧美激情在线免费观看| 亚洲免费在线观看视频| 久久岛国电影| 在线亚洲免费视频| 久久久久在线观看| 亚洲永久免费| 久久先锋影音| 亚洲免费中文| 欧美福利视频一区| 欧美专区在线观看| 欧美二区在线看| 久久天天躁狠狠躁夜夜av| 欧美日韩中文在线| 乱中年女人伦av一区二区| 欧美日韩一区二区在线视频 | 99国产精品自拍| 国产视频一区在线观看一区免费| 欧美激情久久久久久| 国产精品―色哟哟| 一区二区欧美国产| 亚洲精品1区2区| 亚洲日本欧美在线| 久久黄色影院| 欧美一级专区免费大片| 欧美精品激情在线| 欧美激情一区三区| 好吊妞这里只有精品| 亚洲一区二区视频在线观看| 亚洲精品免费一二三区| 久久gogo国模啪啪人体图| 亚洲一级高清| 欧美精品在线免费| 欧美大胆人体视频| 国产一区在线免费观看| 一本到12不卡视频在线dvd| 最新国产の精品合集bt伙计| 欧美一区亚洲二区| 亚洲日本成人网| 亚洲欧美经典视频| 亚洲福利国产| 午夜精品亚洲| 夜夜嗨一区二区| 久久精品国产2020观看福利| 亚洲一区观看| 欧美电影打屁股sp| 久久天天躁狠狠躁夜夜av| 欧美午夜无遮挡| 一本久久精品一区二区| 亚洲国产va精品久久久不卡综合| 欧美永久精品| a4yy欧美一区二区三区| 欧美成人精品在线播放| 久久野战av| 国产精品一区在线观看你懂的| 亚洲福利视频在线| 在线成人小视频| 亚洲永久免费精品| 一区二区日韩| 国产香蕉久久精品综合网| 欧美主播一区二区三区美女 久久精品人 | 狠狠色狠狠色综合日日91app| 亚洲一区黄色| 久久成人免费电影| 红桃av永久久久| 欧美大胆a视频| 一本一本久久a久久精品牛牛影视| 亚洲午夜精品17c| 国产伦精品一区二区三区视频黑人 | 亚洲精品一线二线三线无人区| 香蕉精品999视频一区二区| 亚洲大胆人体视频| 国产精品日韩二区| 欧美日产在线观看| 久久久999精品免费| 一区二区三区www| 欧美成熟视频| 国产一区久久| 欧美日本精品在线| 久久综合色婷婷| 亚洲在线观看视频网站| 亚洲韩日在线| 欧美成人精品一区二区三区| 欧美一区深夜视频| 亚洲深夜激情| 亚洲美女黄网| 亚洲黄色有码视频| 影音欧美亚洲| 激情欧美日韩|