• <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. 

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

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年8月>
            
	
            日一二三四五六
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久精品不卡|
国内精品伊人久久久影院|
一本一道久久精品综合|
国产一区二区精品久久凹凸|
亚洲国产成人精品女人久久久|
久久亚洲AV成人无码软件|
99久久无码一区人妻a黑|
国产免费久久久久久无码|
少妇人妻综合久久中文字幕|
久久久国产精品网站|
久久久这里只有精品加勒比|
久久96国产精品久久久|
久久精品免费一区二区|
99久久精品费精品国产|
亚洲av伊人久久综合密臀性色|
国产精品无码久久四虎|
亚洲色欲久久久综合网东京热|
国产视频久久|
国产精品美女久久久久|
亚洲伊人久久大香线蕉综合图片|
国产精品va久久久久久久|
国产精品免费看久久久|
性高湖久久久久久久久|
伊人久久大香线蕉无码麻豆|
国产日产久久高清欧美一区|
亚洲综合伊人久久综合|
一本色综合网久久|
性色欲网站人妻丰满中文久久不卡|
久久综合成人网|
久久综合伊人77777麻豆|
久久青青草原精品影院|
久久91精品久久91综合|
91久久精品视频|
国产精品内射久久久久欢欢|
狠狠色伊人久久精品综合网|
一本久久a久久精品综合夜夜|
亚洲一区二区三区日本久久九|
999久久久免费国产精品播放|
日韩一区二区久久久久久|
亚洲国产精品久久久久网站|
国产精品99久久久久久www|