• <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 閱讀(312) 評論(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. 

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

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2013年11月>
            
	
            日一二三四五六
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            1234567
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久99精品久久久久久
|
亚洲精品国产综合久久一线|
亚洲午夜久久影院|
欧美成a人片免费看久久|
久久亚洲AV成人无码电影|
青青草国产精品久久久久|
久久久国产亚洲精品|
青青青青久久精品国产h|
久久久国产视频|
91精品国产高清久久久久久91|
青青草原综合久久大伊人导航|
久久w5ww成w人免费|
四虎影视久久久免费|
久久久青草久久久青草|
久久久久se色偷偷亚洲精品av|
91久久精品国产成人久久|
久久精品国产亚洲AV无码偷窥|
久久综合伊人77777|
久久精品国产99国产电影网|
午夜久久久久久禁播电影|
久久精品国产清自在天天线|
青草影院天堂男人久久|
婷婷久久久亚洲欧洲日产国码AV|
亚洲国产成人精品女人久久久
|
久久综合亚洲欧美成人|
无码国内精品久久综合88
|
久久久无码精品亚洲日韩京东传媒|
草草久久久无码国产专区|
精品久久久久久|
99久久久精品|
情人伊人久久综合亚洲|
久久青青草原国产精品免费|
久久久久亚洲AV片无码下载蜜桃
|
久久综合狠狠综合久久97色|
免费国产99久久久香蕉|
青青草原综合久久大伊人精品|
久久91精品国产91久久户|
亚洲精品国产成人99久久|
精品99久久aaa一级毛片|
韩国三级中文字幕hd久久精品|
国产精品狼人久久久久影院|