• <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 閱讀(309) 評論(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年7月>
            
	
            日一二三四五六
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



波多野结衣中文字幕久久|
国产精品久久久99|
亚洲午夜久久久|
久久国产劲爆AV内射—百度|
7777精品久久久大香线蕉|
久久99精品久久只有精品|
久久精品国产99久久久古代|
久久久久人妻精品一区三寸蜜桃|
亚洲综合久久夜AV |
亚洲国产精品成人AV无码久久综合影院|
狠狠久久综合伊人不卡|
亚洲国产精品无码久久SM|
国内精品久久久久久久久|
久久99久久成人免费播放|
精品久久久久久无码中文字幕|
久久久噜噜噜久久|
青青青青久久精品国产h|
色妞色综合久久夜夜|
激情久久久久久久久久|
精品综合久久久久久88小说|
久久青青国产|
欧美噜噜久久久XXX|
人人妻久久人人澡人人爽人人精品|
国产精品久久久久免费a∨|
热re99久久6国产精品免费|
久久久久中文字幕|
亚洲欧美日韩精品久久亚洲区|
中文字幕久久精品无码|
精品久久久久久中文字幕|
久久久婷婷五月亚洲97号色
|
久久久久久曰本AV免费免费|
久久精品国产亚洲AV香蕉|
久久亚洲国产欧洲精品一|
久久综合视频网|
亚洲综合久久夜AV |
99久久久国产精品免费无卡顿
|
国产精品美女久久久久久2018|
精品久久久久久国产牛牛app|
亚洲av日韩精品久久久久久a|
久久久久国产精品嫩草影院|
久久久亚洲欧洲日产国码二区|