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

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
              1#include <cstdio>
              2#include <cstring>
              3#include <algorithm>
              4using namespace std;
              5
              6const int INTMAX = 1000;
              7const int SIZE = 20001;
              8const int MAXN = 1001;
              9
             10struct EDGE
             11{
             12    int x, y, len;
             13
             14}            edge[SIZE];
             15
             16bool cmp1 ( const EDGE& a, const EDGE& b )
             17{
             18    if ( a.x != b.x )
             19        return ( a.x < b.x );
             20    else
             21        return ( a.y <= b.y );
             22}
             23bool cmp2 ( const EDGE& a, const EDGE& b )
             24{
             25    return ( a.len <= b.len );
             26}
             27
             28int N, P, K;
             29int arr[SIZE], mark[MAXN], temp[MAXN], biArr[SIZE];
             30
             31bool Dij(const int& length)
             32{
             33    int i, j, k, t, min;
             34
             35    for ( i = 0; i < P; ++i )
             36    {
             37        if ( edge[i].len > length )
             38            arr[i] = 1;
             39        else
             40            arr[i] = 0;
             41    }
             42
             43    temp[1] = -1;
             44    for ( i = 2; i <= N; ++i )
             45    {
             46        temp[i] = INTMAX; 
             47    }
             48
             49    for ( i = mark[1]; edge[i].x == 1; ++i )
             50    {
             51        temp[edge[i].y] = arr[i];
             52    }
             53
             54    for ( i = 2; i <= N; ++i )
             55    {
             56        min = INTMAX;
             57        k = 1;
             58        for ( j = 2; j <= N; ++j )
             59        {
             60            if ( temp[j] != -1 && temp[j] < min )
             61            {
             62                min = temp[j];
             63                k = j;
             64            }
             65        }
             66        for ( j = mark[k]; edge[j].x == k; ++j )
             67            if ( temp[edge[j].y] > temp[k] + arr[j] && temp[k] != -1 )
             68                temp[edge[j].y] = temp[k] + arr[j];
             69        
             70        if ( k == N )
             71            t = temp[k];
             72        temp[k] = -1;
             73    }
             74
             75    if ( t <= K )
             76        return true;
             77    return false;
             78}
             79
             80void Solve()
             81{
             82    int i, j, mid, left, right;
             83
             84    sort( edge, edge + P, cmp2 );
             85
             86    j = 0;
             87    biArr[j++] = 0;
             88    biArr[j++] = edge[0].len;
             89    for ( i = 1; i < P; ++i )
             90    {
             91        if ( edge[i].len != edge[i - 1].len )
             92            biArr[j++] = edge[i].len;
             93    }
             94
             95    memset(mark, 0, sizeof(mark));
             96    sort(edge, edge + P, cmp1);
             97
             98    mark[edge[0].x] = 0;
             99    for ( i = 1; i < P; ++i )
            100    {
            101        if ( edge[i].x != edge[i - 1].x )
            102            mark[edge[i].x] = i;
            103    }
            104
            105
            106    left = 0, right = j - 1;
            107    while ( left <= right )
            108    {
            109        mid = (left + right) >> 1;
            110        if ( Dij( biArr[mid] ) )
            111            right = mid - 1;
            112        else
            113            left = mid + 1;
            114            
            115    }
            116
            117    if ( Dij( biArr[left] ) )
            118        printf("%d\n", biArr[left]);
            119    else
            120        printf("-1\n");
            121}
            122
            123int main()
            124{
            125//    freopen("1.txt", "r", stdin);
            126
            127    int i, j, x, y, l;
            128
            129    scanf("%d %d %d", &N, &P, &K);
            130
            131    for ( i = 0, j = 0; i < P; ++i )
            132    {
            133        scanf("%d %d %d", &x, &y, &l);
            134        edge[j].x = x; edge[j].y = y; edge[j++].len = l;
            135        edge[j].x = y; edge[j].y = x; edge[j++].len = l;
            136    }
            137
            138    P <<= 1;
            139
            140    Solve();
            141
            142    return 0;
            143}
            

	
            
	
	
            
		posted on 2009-03-19 21:00 巫 閱讀(420) 評論(0)  編輯 收藏 引用  所屬分類: 圖論 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久夜色精品国产亚洲|
亚洲欧美日韩精品久久|
99久久www免费人成精品
|
亚洲国产精品无码久久久不卡|
亚洲国产精品久久久久网站|
久久综合九色综合网站|
久久精品免费全国观看国产|
久久久久亚洲精品天堂久久久久久|
久久婷婷国产麻豆91天堂|
91精品国产色综合久久|
久久99国产综合精品女同|
午夜不卡久久精品无码免费|
无码人妻久久一区二区三区免费丨|
91麻豆国产精品91久久久|
综合人妻久久一区二区精品|
人妻中文久久久久|
亚洲午夜无码AV毛片久久|
欧洲国产伦久久久久久久|
亚洲伊人久久成综合人影院
|
91精品国产高清久久久久久国产嫩草
|
伊人久久大香线蕉无码麻豆|
亚洲精品国产第一综合99久久|
亚州日韩精品专区久久久|
亚洲国产精品成人久久蜜臀|
久久久久久久综合狠狠综合|
久久精品国产99国产精品导航|
欧美va久久久噜噜噜久久|
99热成人精品热久久669|
一本伊大人香蕉久久网手机|
久久精品国产清自在天天线|
国产精品久久新婚兰兰|
久久精品国产亚洲精品2020|
狠狠色丁香婷婷综合久久来|
18禁黄久久久AAA片|
久久香蕉国产线看观看精品yw|
97久久香蕉国产线看观看|
精品国产热久久久福利|
欧美亚洲国产精品久久高清
|
亚洲国产精品久久久久婷婷老年|
久久男人AV资源网站|
久久婷婷成人综合色综合|