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

            分類：最短路

            題目分析與算法原型
                     將需要搬動的開關(guān)的節(jié)點的權(quán)值設(shè)為1，不需要搬動的開關(guān)設(shè)為0，不可達的設(shè)為一個充分大的數(shù)，這樣一來，此題就轉(zhuǎ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 閱讀(310) 評論(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
            

            

					

            導航
            

					

            統(tǒng)計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



欧美亚洲色综久久精品国产|
亚洲国产精品久久久久网站|
99久久精品免费观看国产|
精品久久人人爽天天玩人人妻|
精品乱码久久久久久夜夜嗨
|
伊人久久大香线蕉综合Av|
久久性生大片免费观看性|
久久精品亚洲男人的天堂|
精品久久人人妻人人做精品|
狠狠色综合久久久久尤物|
精品久久久久久久久久久久久久久|
品成人欧美大片久久国产欧美...|
 久久综合狠狠综合久久激情 |
国产成人久久精品麻豆一区|
久久久久亚洲AV无码专区网站|
午夜视频久久久久一区
|
国产午夜久久影院|
久久成人影院精品777|
九九热久久免费视频|
97精品伊人久久大香线蕉|
久久香综合精品久久伊人|
99久久久久|
久久精品桃花综合|
久久国产精品一国产精品金尊|
国产一级做a爰片久久毛片|
欧美一级久久久久久久大片|
久久久久免费精品国产|
久久久久国产精品|
精品国产日韩久久亚洲|
1000部精品久久久久久久久|
久久久久久国产a免费观看不卡|
久久久一本精品99久久精品88|
国产精品99久久99久久久|
欧美无乱码久久久免费午夜一区二区三区中文字幕|
久久夜色撩人精品国产|
久久99国内精品自在现线|
久久综合色区|
一本伊大人香蕉久久网手机|
少妇熟女久久综合网色欲|
久久亚洲精品中文字幕三区|
国色天香久久久久久久小说|