poj 2449 Remmarguts' Date (K 단락, A * 알고리즘)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 100010;

struct node
{
	int u,v,w;
};

int s,t,k;
int n,m;
vector <struct node> edge[maxn],edge1[maxn]; //          
int dis[maxn]; //           
int time[maxn];//          
int ans;

bool operator > (const struct node &a, const struct node &b)
{
	return a.w+dis[a.v] > b.w + dis[b.v];
}
priority_queue < node, vector<node>, greater<node> >q;

void init()
{
	for(int i = 1; i <= n; i++)
	{
		edge[i].clear();
		edge1[i].clear();
	}
}

//spfa             
void spfa() 
{
	int inque[maxn];
	queue<int> que;
	while(!que.empty()) que.pop();
	memset(inque,0,sizeof(inque));
	memset(dis,INF,sizeof(dis));

	dis[t] = 0;
	inque[t] = 1;
	que.push(t);

	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		inque[u] = 0;
		for(int i = 0; i < (int)edge1[u].size(); i++)
		{
			int v = edge1[u][i].v;
			int w = edge1[u][i].w;
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if(!inque[v])
				{
					inque[v] = 1;
					que.push(v);
				}
			}
		}
	}
}

void solve()
{
	while(!q.empty()) q.pop();
	memset(time,0,sizeof(time));
	struct node tmp;
	bool flag = false;
	
	//     
	tmp.v = s;
	tmp.w = 0;
	q.push(tmp);

	while(!q.empty())
	{
		struct node u = q.top();
		q.pop();

		time[u.v]++;
		if(time[u.v] >= k) //        K 
		{
			if(u.v == t) //     ，         
			//    ,      K  ，   K+1      
			{
				if(t != s || (t == s && time[u.v] == k+1))
				{
					flag = true;
					ans = u.w;
					break;
				}
			}
			if(time[u.v] > k)//      ，       K       
				continue;
		}
		
		int now = u.v;
		for(int i = 0; i < (int)edge[now].size(); i++)
		{
			struct node tmp;
			tmp.v = edge[now][i].v;
			tmp.w = u.w + edge[now][i].w;
			q.push(tmp);
		}
	}
	if(!flag)
		ans = -1;
}

int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		init();
		int u,v,w;
		for(int i = 1; i <= m; i++)
		{
			scanf("%d %d %d",&u,&v,&w);
			edge[u].push_back( (struct node){u,v,w} );
			edge1[v].push_back( (struct node) {v,u,w} );
		}
		scanf("%d %d %d",&s,&t,&k);
		
		spfa();

		solve();
		
		printf("%d
",ans);

	}

	return 0;
}