• <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 1847
		
            
		
            2009年7月24日

            題目鏈接：PKU 1847 Tram

            分類：最短路

            題目分析與算法原型
                     將需要搬動的開關的節點的權值設為1，不需要搬動的開關設為0，不可達的設為一個充分大的數，這樣一來，此題就轉換為最短路徑問題了，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 閱讀(316) 評論(2)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				# re: pku 1847
					
						2009-09-10 18:02
					
				Johnnx
			
            
			
            
				if(j==1)a[i][t]=0;
            你代碼里的這一句是什么意思，我不太明白？但卻是必須的。能給我解釋一下嗎  回復  更多評論
				  
			
            
		
			
            
				# 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. 

            注意題目中的這句話  回復  更多評論
				  
			
            
		

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年9月>
            
	
            日一二三四五六
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



欧美久久亚洲精品|
精品国产91久久久久久久|
久久久久亚洲av成人无码电影
|
久久综合狠狠综合久久97色|
亚洲色欲久久久久综合网|
久久精品aⅴ无码中文字字幕不卡|
…久久精品99久久香蕉国产|
久久精品国产精品亜洲毛片|
日韩精品久久无码人妻中文字幕|
久久国产精品99精品国产987|
久久亚洲精品国产亚洲老地址|
精品久久久久久无码中文字幕一区|
久久国产精品免费一区二区三区|
精品一二三区久久aaa片|
亚洲成av人片不卡无码久久|
久久精品人人做人人爽电影|
久久精品国产免费观看三人同眠|
久久精品中文字幕一区|
久久99精品久久久久子伦|
97久久国产露脸精品国产|
久久免费视频6|
久久久不卡国产精品一区二区|
成人国内精品久久久久一区|
日韩精品无码久久久久久|
波多野结衣久久精品|
色天使久久综合网天天|
久久久久噜噜噜亚洲熟女综合|
97精品伊人久久大香线蕉app|
99精品国产综合久久久久五月天|
久久久久亚洲AV片无码下载蜜桃|
久久天天日天天操综合伊人av|
久久国产成人|
久久国产综合精品五月天|
国产精品成人99久久久久|
久久成人永久免费播放|
久久人人爽人人爽人人片AV麻豆|
久久久久久久尹人综合网亚洲|
国产成人无码精品久久久免费|
久久www免费人成看国产片|
伊人久久大香线蕉综合网站|
精品国产乱码久久久久软件|