poj 2449 Remmarguts' Date (K 단락, A * 알고리즘)
2705 단어 최 단 로
대체적으로 제목: 출발점 에서 종점 까지 의 K 단락 을 구 하 는 방향 도 를 제시 합 니 다.
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1233 또는 원활 한 공정 최소 생 성 트 리 (prim 알고리즘 + kruskal 알고리즘)그럼 이 연결 서브 맵 은 G 의 최소 생 성 트 리 입 니 다.최소 생 성 트 리 를 구 하 는 흔 한 알고리즘 은 Prim 알고리즘 입 니 다. 욕심 전략 을 사용 하기 때문에 집합 S 에 새로운 정점 을 추가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.