【解題報告】POJ 2449 Remmarguts'Date--図第kへ短絡(重辺あり)

/*
	POJ 2449 Remmarguts' Date --     k  (   )
	         (Dijkstra)  
	        (      /A*)
*/

#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <assert.h>
//#include <ctime>
using namespace std;
#define CLR(c,v) memset(c,v,sizeof(c))

typedef pair<int,int> pii;
typedef long long ll;
const double eps = 1e-6;
const int N = 1e3 + 10;
const int INF =  (0x03ffffff);
const int inf = -(0x03ffffff);

// m1[id][i].first   (id )  i    (first )      .second 
// m1    ，m2    
vector<pii> m1[N],m2[N]; 
int G[N]; //     
int e,s,k; // e   s    k 
struct P{
	int p,g,h;
	P(){}
	P(const P& Val){p=Val.p;g=Val.g;h=Val.h;}
	P(int p,int g,int h):p(p),g(g),h(h){}
	bool operator < (const P& Val) const{ //  g+h    
		return Val.g+Val.h < g+h;
	}     
};

void pre(int n){
	//Dijkstra           
	bool vis[N];
	CLR(vis,0);
	for(int i = 1 ; i < N ; i++)G[i] = INF;
	G[e] = 0;
	for(int i = 1 ; i <= n ; i++){
		int minid = 0;
		for(int j = 1 ; j <= n ; j++){
			if(vis[j] || (minid && G[minid]<=G[j]) )continue;
			minid = j;
		}

		vis[minid] = 1;
		int size = m2[minid].size();
		for(int j = 0 ; j < size ; j++){
			if( G[ m2[minid][j].first ] > G[minid]+m2[minid][j].second)
				G[ m2[minid][j].first ] = G[minid]+m2[minid][j].second;
		}
	}
}

int solve(int n){
	//      ，       push   ,H()        ,G()        
	//     G()+H()    
	//    k     ,   G()+H()   
	priority_queue <P> q;
	int ts[N];CLR(ts,0); // ts[i]   i       ,          ' '  
	P now , b(s,G[s],0);
	q.push( b );
	while( !q.empty()){
		now = q.top();q.pop();
		if(++ts[now.p] > k)continue; //           k      
		if(now.p == e && ts[now.p] == k )return now.h+now.g;
		int size = m1[now.p].size();
		for(int i = 0 ; i < size ; i++){
			// (now.p),(next.first)          next.second
			pii next = m1[now.p][i];
			b = P(next.first , G[next.first], now.h+next.second);
			q.push( b );
		}
	}
	return -1;
}

int main(){
	//freopen("in.txt","r",stdin);
	int n,m;
	while(cin >> n >> m){
		for(int i = 0 ; i < m ; i++){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			m1[a].push_back(make_pair(b,c));
			m2[b].push_back(make_pair(a,c));
		}
		cin >> s >> e >> k;
		if(s==e)k++;  //                  ，         
		pre(n);
		cout << solve(n) << endl;
		for(int i = 0; i < N ; i++)
			m1[i].clear(),m2[i].clear();
	}
	return 0;
}