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

            久久夜色精品国产噜噜麻豆| 精品久久无码中文字幕| 日本三级久久网| 久久久久无码中| 狠狠综合久久综合88亚洲| 777午夜精品久久av蜜臀| 久久精品国产亚洲av影院| 久久久久亚洲AV无码去区首| 三上悠亚久久精品| 久久久精品国产亚洲成人满18免费网站 | 久久电影网一区| 久久精品极品盛宴观看| 丰满少妇人妻久久久久久4| 伊人久久大香线蕉AV色婷婷色| 青青青伊人色综合久久| 久久精品国产亚洲AV忘忧草18| 亚洲乱亚洲乱淫久久| 色综合久久中文字幕无码| 久久婷婷五月综合97色直播| AV狠狠色丁香婷婷综合久久 | 久久99精品久久久久久久久久| 欧美伊人久久大香线蕉综合69| 国产成人久久AV免费| 亚洲AV乱码久久精品蜜桃| 久久午夜福利无码1000合集| 国产福利电影一区二区三区久久久久成人精品综合 | 18岁日韩内射颜射午夜久久成人| 成人综合久久精品色婷婷| 久久精品国产第一区二区| 国内精品久久久久久麻豆 | 91超碰碰碰碰久久久久久综合| 久久亚洲AV成人无码国产| 国内高清久久久久久| 精品伊人久久久| 亚洲香蕉网久久综合影视| 精品国产乱码久久久久软件| 久久国产AVJUST麻豆| 少妇人妻综合久久中文字幕| 无码人妻久久一区二区三区蜜桃| 久久精品国产男包| 久久人爽人人爽人人片AV|