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

            Remmarguts' Date poj 2449 K短路

            Posted on 2012-04-26 22:05 lenohoo 閱讀(363) 評論(1)  編輯 收藏 引用
            Remmarguts' Date

            Description

            "Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little ducks' head, he told them a story.

            "Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."

            "Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"

            Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!

            DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate.

            Input

            The first line contains two integer numbers N and M (1 <= N <= 1000, 0 <= M <= 100000). Stations are numbered from 1 to N. Each of the following M lines contains three integer numbers A, B and T (1 <= A, B <= N, 1 <= T <= 100). It shows that there is a directed sideway from A-th station to B-th station with time T.

            The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000).

            Output

            A single line consisting of a single integer number: the length (time required) to welcome Princess Uyuw using the K-th shortest path. If K-th shortest path does not exist, you should output "-1" (without quotes) instead.

            Sample Input

            2 2 1 2 5 2 1 4 1 2 2 

            Sample Output

            14

            Source

            POJ Monthly,Zeyuan Zhu

            #include<cstdio>
            #include
            <cstring>
            #include
            <iostream>
            #include
            <vector>
            #include
            <queue>
            #include
            <algorithm>
            using namespace std;
            #define re(i,n) for(int i=0;i<n;i++)
            #define re2(i,n) for(int i=1;i<=n;i++)
            #define pb push_back
            const int MAXN = 1001;
            const int inf = 999999999;
            struct nod{
                
            int x,val;
            };
            struct cmp{
                
            bool operator()(nod a,nod b){
                    
            return a.val>b.val;
                }
            };
            int N,M,S,T,K,dist[MAXN],out[MAXN];
            vector
            <nod> g[MAXN],r[MAXN];
            priority_queue
            <nod,vector<nod>,cmp> Q;
            void dijkstra(){
                
            bool vi[MAXN];
                re2(i,N) vi[i]
            =0,dist[i]=inf;
                dist[T]
            =0;
                
            while(1){
                    
            int k=-1;
                    re2(i,N) 
            if(!vi[i] && (k==-1 || dist[i]<dist[k])) k=i;
                    
            if(k==-1break;
                    vi[k]
            =1;
                    re(i,r[k].size()){
                        nod u
            =r[k][i];
                        
            if(!vi[u.x] && dist[u.x]>dist[k]+u.val) dist[u.x]=dist[k]+u.val;
                    }
                }
            }
            int astar(){
                dijkstra();
                nod v;
                v.x
            =S,v.val=dist[S];
                Q.push(v);
                re2(i,N) 
            out[i]=0;
                
            while(!Q.empty() && out[T]<K){
                    v
            =Q.top();Q.pop();
                    
            if(out[v.x]>=K) continue;
                    
            if(v.x==T){
                        
            out[v.x]++;
                        
            if(out[v.x]==K) return v.val;
                    }
                    re(i,g[v.x].size()){
                        nod u
            =g[v.x][i];
                        
            if(out[u.x]>=K) continue;
                        u.val
            =v.val-dist[v.x]+u.val+dist[u.x];
                        Q.push(u);
                    }
                }
                
            return -1;
            }
            int main(){
                
            while(cin>>N>>M){
                    
            int a,b,w;
                    re2(i,N) g[i].clear(),r[i].clear();
                    re(i,M){
                        cin
            >>a>>b>>w;
                        nod tmp;
                        tmp.x
            =b,tmp.val=w;
                        g[a].pb(tmp);
                        tmp.x
            =a;
                        r[b].pb(tmp);
                    }
                    cin
            >>S>>T>>K;
                    
            if(S==T) K++;
                    
            int ans=astar();
                    cout
            <<ans<<endl;
                }
                
            return 0;
            }

            Feedback

            # re: Remmarguts' Date poj 2449 K短路  回復  更多評論   

            2012-04-27 07:06 by lenohoo
            注意s==t的時候要k++啊

            posts - 3, comments - 1, trackbacks - 0, articles - 16

            Copyright © lenohoo

            精品国产福利久久久| 久久久国产打桩机| 青青国产成人久久91网| 91精品国产91热久久久久福利| 久久er国产精品免费观看8| 香蕉aa三级久久毛片| 91久久精一区二区三区大全| 国产精品热久久毛片| 伊人久久综合精品无码AV专区| 久久精品国内一区二区三区| 一级女性全黄久久生活片免费 | 久久一区二区三区免费| 国产亚洲精久久久久久无码77777 国产亚洲精品久久久久秋霞 | 色欲综合久久躁天天躁蜜桃| 7国产欧美日韩综合天堂中文久久久久| 欧美亚洲另类久久综合婷婷| 国产精品久久成人影院| 亚洲av伊人久久综合密臀性色| 国产精品久久久久久久久久免费| 新狼窝色AV性久久久久久| 久久亚洲国产成人精品无码区| 俺来也俺去啦久久综合网| 91麻豆国产精品91久久久| 精品久久综合1区2区3区激情| 一本久道久久综合狠狠爱| 亚洲va久久久久| 午夜精品久久久久久影视777| 久久精品国产WWW456C0M| 久久国产精品国产自线拍免费 | 久久精品国产99久久无毒不卡 | 久久免费视频一区| 久久精品国产亚洲一区二区三区 | 91超碰碰碰碰久久久久久综合| 蜜臀av性久久久久蜜臀aⅴ| 午夜精品久久久久久影视riav| 久久久久久无码国产精品中文字幕 | 亚洲国产欧洲综合997久久| 中文精品久久久久人妻不卡| 狠狠色丁香久久婷婷综合| 伊人久久精品无码av一区| 色88久久久久高潮综合影院 |