POJ 2249 k 단락 낙 곡 P2349 피라미드 평론 Astar

그동안 Astar 알고리즘 을 쓰 려 고 했 는데 최근 에 시험 이 좀 지체 되 었 기 때 문 입 니 다.
Astar 의 기본 적 인 의 미 를 약술 하 자. BFS 와 평가 함 수 를 바탕 으로 하 는 더 좋 은 BFS;일반적인 BFS 와 의 주요 차이 점 은 Astar 가 우선적으로 검색 하 는 순서 성 을 가지 고 있 기 때문에 이 성질 을 이용 하면 엉뚱 해 보 이 는 XD 문 제 를 해결 할 수 있다.
우리 가 언급 한 바 와 같이 BFS 와 Astar 의 차 이 는 바로 평가 함수 (일반적으로 f 라 고 부른다) 에 있다. 그 문 제 는 좋 은 f 를 어떻게 설계 하 느 냐 에 달 려 있다.
먼저 f 의 성질 을 명 확 히 하고 간략하게 증명 한다.  
(실제 값 (ans) 을 g 로 정의 합 니 다) (f = 현재 대가 와 미래 가능 한 대가)
1. f < = g, 그리고 f = = g 시 BFS 가 가장 쉽게 검색 할 수 있 습 니 다.
         증명: 1. 평가 함수 가 정 답 을 정확하게 평가 한 것 이 분명 하 다. 그러면 이 경 로 를 따라 반드시 정 해 될 것 이다.(이때 f 는 보통 실시 간 업데이트)
                   2. f < = g: Astar 는 priority quue 를 바탕 으로 이 루어 집 니 다. f 가 클 수록 (우) 먼저 업데이트 되 고 f > g 이면 현재 오류 경로 로 검색 합 니 다.
                      이 때 f 가 대표 하 는 경 로 는 최 적 화 (또는 정 해) 가 아니 기 때문에 ans 업데이트 판단 이 없 으 면 WA, 판단 이 있 으 면 BFS (이때 때 문) 보다 못 합 니 다.                         난서 탐색)
2. f 가 0 에 가 까 워 질 수록 느 리 고 최 적 화 된 특성 을 가지 지 않 는 다. 이때 우 리 는 ans 를 판단 하 는 더 좋 은 조건 (바로 BFS 이다) 을 추가 해 야 한다.
f 의 개인 적 인 이해: 여러 가지 요구 의 더 좋 은 조건 을 균형 시 켜 전체적인 최 우수 에 이 르 도록 한다 (모든 최 우수 가 아니다).
기초 지식 을 다 말 하고 지금 k 단락 을 고려 해 보 세 요.
우 리 는 모두 알 고 있 습 니 다. 가장 짧 은 길 은 spfa 한 번 이면 됩 니 다.가장 긴 길 은 같은 이치 이다.
그러면 다음 단락 은 가장 짧 은 길 을 바탕 으로 min (x 변 - > y 변 (비교적 큰) 을 희생 해 야 한다.
2 차 단락 동 리;
but, k 단락 은 이것 과 큰 관계 가 없 지만 XD 는 우리 에 게 아 이 디 어 를 주 었 다.
만약 우리 가 실시 간 으로 방금 min 을 계산 해 낸다 면, 이 min 은 아마 그 몇 개의 변 일 것 이다.
emm, 알고리즘 이 왔 습 니 다:
 분명히 우 리 는 x 시 까지 얼마나 걸 렸 는 지, 그리고 그 다음 에 내 가 가장 적 게 얼마나 쓸 수 있 는 지 알 고 싶 습 니 다.
 이렇게 하면 내 가 end 로 업 데 이 트 했 을 때 내 가 얼마나 썼 는 지 알 수 있 고 비교적 짧 은 노선 으로 도착 했다.
 즉: f = 현재 의 대가 (g) + end 까지 의 최 단 로 (h); /사실 g 는 제거 할 수도 있 고 뛸 수도 있 습 니 다. 여 기 는 f 의 실제 변화 에 적응 하여 f < = g (더욱 가 까 워 짐) 에 도달 하여 효율 을 가속 화하 기 위해 서 입 니 다.
 그래서 spfa 는 반대로 가장 짧 은 길 로 h 를 얻 고 BFS + pq 는 g 를 얻 습 니 다.(ans) / / and, f 가 아주 잘 쓰 면 처음으로 end 까지 매우 잘 풀 립 니 다 (이 문제 뿐만 아니 라)
 아래 에 코드 를 붙 여 주세요. (emmm,,, 길지 않 습 니 다. 주석 을 달 지 않 겠 습 니 다. 하 XD)

#include
#include
#include
#include
using namespace std;
#define M 2000500
#define N 10000
#define INF 0xfffffff
int n,m,k;
int dis[N],vis[N];
int head[M],nxt[M],ver[M],val[M],cnt=0;
int head2[M],nxt2[M],ver2[M];
void add(int x,int y,int c){
	nxt[++cnt]=head[x];
	ver[cnt]=y;
	val[cnt]=c;
	head[x]=cnt;
	nxt2[cnt]=head2[y];	
	ver2[cnt]=x;
	head2[y]=cnt;
	return ;
}
struct node{
	int g,h,f;int to;
	bool friend operatorb.f;
	}
};
struct node2{ //acer YY    py    
	int cost,num;
	bool friend operatory.cost;
	}
};
void spfa(int s){
	fill(dis+1,dis+1+n,INF);
	memset(vis,0,sizeof(vis));
	vis[s]=1;dis[s]=0;
	node2 now,next;now.cost=0,now.num=s;
	priority_queueq;q.push(now);
	while(q.size()){
		next=q.top();q.pop();vis[next.num]=0;
		for(int i=head2[next.num];i;i=nxt2[i]){
			if(dis[ver2[i]]>dis[next.num]+val[i]){
				dis[ver2[i]]=dis[next.num]+val[i];
				if(!vis[ver2[i]]){
					vis[ver2[i]]=1;
					now.cost=dis[ver2[i]];
					now.num=ver2[i];
					q.push(now);
				}
	}}}return ;
}
int Astar(int s,int end){
	int tot=0;node e,t;
	priority_queueQ;
	if(s==end)k++;
	if(dis[end]==INF)return -1; 
	e.to=s;e.g=0;e.h=dis[s];e.f=e.g+e.h;
	Q.push(e);
	while(Q.size()){
		e=Q.top();Q.pop();
		if(e.to==end)tot++;if(tot==k)return e.g;
		for(int i=head[e.to];i;i=nxt[i]){
			t.to=ver[i];
			t.g=e.g+val[i];
			t.h=dis[ver[i]];
			t.f=t.g+t.h;
			Q.push(t);
		}
	}return -1;
}
void clean(){
	fill(head+1,head+1+n,0);
	fill(head2+1,head2+1+n,0);	
	cnt=0;
}
int main(void){
	int x,y,w,s,e;
	while(scanf("%d%d",&n,&m)!=EOF){
		clean();
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&x,&y,&w);
			add(x,y,w);
		}
		scanf("%d%d%d",&s,&e,&k);
		spfa(e);
		int ans=Astar(s,e);
		printf("%d
",ans); 
	}
}

그리고 낙 곡 의 P2349 피라미드.
        라 라 는 피라미드 지 도 를 받 고 상 자 를 열 때 기관 을 만 났 다.
, and 는 라 라 의 도망 속 도 를 반 으로 줄 이 는 독 연 기 를 내 뿜 었 다.그리고 우리 라 라 는 뛰 기 시작 했다.
문제 에서 제시 한 것 은 쌍방 향 변 으로 연결 이 보장 되 는 것 같다.(연결 되 지 않 아 도 괜찮아, 라 라 는 날 수 있 을 까?)
라 라 는 최 악의 경우 얼마나 걸 리 는 지 알 고 싶 어 한다.(한참 을 생각 했 는데 그 걸 왜 알 고 있 는 지...)
         so. 제목 은 무방 향도 와 st 와 end 를 정 하고 길 을 구하 여 그 경로 의 최대 경로 x2 를 정 한 후 비용 이 가장 적 게 든다.
 분명히 우 리 는 문제 에서 두 가지 조건 을 동시에 유지 한 것 을 발견 할 수 있다. 1. 총 비용 이 가장 적 고 2. 도로 max 가 가장 적다.
 f = 현재 경로 와 + 도로 max + end 까지 의 최소 값
 그리고 poj 2249, Astar 를 따라 일 을 끝 냅 니 다 ~;)

#include
using namespace std;
#define M 100000
#define INF 0x3f3f3f3f
int head[M],nxt[M],ver[M],w[M],cnt=0;
void add(int x,int y,int c){nxt[++cnt]=head[x],head[x]=cnt,ver[cnt]=y,w[cnt]=c;return;}
int dis[M],vis[M];
struct node {
    int f,g,h,num;
    bool friend operator < (node  a,node  b){
        return a.f>b.f;
    }
}; 
void BFS(int s){
    memset(vis,0,sizeof(vis));
    memset(dis,INF,sizeof(dis));
    dis[s]=0;vis[s]=1;
    queueq;q.push(s);
    while(q.size()){
        int now=q.front();q.pop();vis[now]=0;
        for(int i=head[now];i;i=nxt[i]){
            if(dis[ver[i]]>dis[now]+w[i]){
                dis[ver[i]]=dis[now]+w[i];
                if(!vis[ver[i]]){
                    vis[ver[i]]=1;
                    q.push(ver[i]);
                }
            }
        }
    }
}
void Astar(int s,int n){
    node e,t;
    priority_queueQ;
    e.h=0;e.g=0;e.f=e.h;e.num=s;
    Q.push(e);
    while(Q.size()){
        e=Q.top();Q.pop();
        if(e.num==n){
            printf("%d
",e.g+e.h);
            return;
        }
        for(int i=head[e.num];i;i=nxt[i]){
            t.h=e.h+w[i];
            t.g=max(e.g,w[i]);
            t.f=t.g+t.h+dis[ver[i]];
            t.num=ver[i];
            Q.push(t);
        }
    }
}
int main(void){
    int n,m,x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);add(y,x,c);
    }
    BFS(n);
    Astar(1,n);
}

and acer 는 PY 의 대기 열 최 적 화 를 썼 습 니 다. BFS, spfa 에 유용 합 니 다. 친구 체인: PY 최적화 XD