차 단락 알고리즘:
두 가지 비교적 간단하게 단락 을 실현 하 는 사상 이 있다.
방법 1: dijkstra 알고리즘 으로 시작 하여 [최 단 로 배열 (dis1 [])] 과 [차 단락 배열 (dis2 []]]] 을 동시에 유지 합 니 다.
방법 2: dijkstra 알고리즘 을 사용 하여 각각 두 개의 dis1 [] 배열 과 dis2 [] 배열 은 각각 출발점 과 종점 에서 시작 하 는 최 단 로 를 유지 합 니 다. 그리고 모든 변 을 매 거 합 니 다. 변 의 두 점 을 출발점 과 종점 에 연결 하여 최 단 로 와 같 는 지, 같 지 않 으 면 건 너 뛰 고 같 지 않 으 면 업데이트 와 차 단락 (Inf) 은 min 을 가 져 옵 니 다.
제목: POJ - 3255
방식 1:
tips: 그 중 if (dis2 [v] < w) continue;이 말 이 true 일 때 현재 노드 v 의 차 단락 이 이미 업데이트 되 었 음 을 설명 합 니 다. 만약 에 w 가 차 단락 보다 크다 면 이것 은 틀림없이 > = 세 번 째 단락 이 고 업데이트 할 필요 가 없습니다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int Maxn = 1e5 + 7;
const int Inf = 1e9 + 7;
int N , M;
int dis1[Maxn] , dis2[Maxn];
struct node{
int v , w;
friend bool operator < (node a , node b){
return a.w > b.w;
}
};
vector G[Maxn];
void Dijkstra(){
priority_queue que;
fill(dis1 , dis1+N+1 , Inf);
fill(dis2 , dis2+N+1 , Inf);
int start = 1;
dis1[start] = 0;
que.push((node){start , 0});
node q;
int v , w;
while(!que.empty()){
q = que.top(); que.pop();
v = q.v , w = q.w;
if(dis2[v] < w) continue;
int to_v , to_w;
for(int i = 0 ; i < G[v].size() ; i++){
to_v = G[v][i].v , to_w = G[v][i].w + w;
if(dis1[to_v] > to_w){
que.push((node){to_v , to_w});
swap(dis1[to_v] , to_w);
}
if(dis2[to_v] > to_w && dis1[to_w] < to_w){
dis2[to_v] = to_w;
que.push((node){to_v , to_w});
}
}
}
}
int main()
{
while(~scanf(" %d %d",&N,&M)){
for(int i = 1 ; i <= M ; i++){
int u , v , w; scanf(" %d %d %d",&u,&v,&w);
G[u].push_back((node){v,w});
G[v].push_back((node){u,w});
}
Dijkstra();
printf("%d 방식 2:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int Maxn = 1e5 + 7;
const int Inf = 1e9 + 7;
int N , M , cnt , ans;
int start = 1 , End = N;
int dis1[Maxn] , dis2[Maxn];
bool vis[Maxn];
struct node{
int v , w;
friend bool operator < (node a , node b){
return a.w > b.w;
}
};
struct edge{
int x , y , w;
}A[Maxn << 1];
vector G[Maxn];
void GetDis(int op){
priority_queue que;
if(!op) que.push((node){start , 0});
else que.push((node){End , 0});
int v , w;
node q;
while(!que.empty()){
q = que.top(); que.pop();
v = q.v , w = q.w;
if(vis[v]) continue;
vis[v] = true;
int to_v , to_w;
for(int i = 0 ; i < G[v].size() ; i++){
to_v = G[v][i].v , to_w = G[v][i].w + w;
if(!op && dis1[to_v] > to_w){
dis1[to_v] = to_w;
que.push((node){to_v , to_w});
} else if(op && dis2[to_v] > to_w){
dis2[to_v] = to_w;
que.push((node){to_v , to_w});
}
}
}
}
void Dijkstra(){
fill(dis1 , dis1+N+1 , Inf);
fill(dis2 , dis2+N+1 , Inf);
start = 1 , End = N;
dis1[start] = dis2[End] = 0;
fill(vis , vis+N+1 , false);
GetDis(0);
fill(vis , vis+N+1 , false);
GetDis(1);
}
void FindCdl(){
int flag = dis1[End];
int x , y , w;
ans = Inf;
for(int i = 1 ; i <= cnt ; i++){
x = A[i].x , y = A[i].y , w = A[i].w;
int temp = dis1[x] + dis2[y] + w;
if(temp == flag) continue;
else ans = min(ans , temp);
}
}
int main()
{
while(~scanf(" %d %d",&N,&M)){
cnt = 0;
for(int i = 1 ; i <= M ; i++){
int u , v , w; scanf(" %d %d %d",&u,&v,&w);
G[u].push_back((node){v,w});
G[v].push_back((node){u,w});
A[++cnt].x = u , A[cnt].y = v , A[cnt].w = w;
A[++cnt].x = v , A[cnt].y = u , A[cnt].w = w;
}
Dijkstra();
FindCdl();
printf("%d 제 K 단락:
제 K 단락 사실은 BFS + A * (A * = = = 계발 식 검색 = = 가지치기 최적화)
우선 종점 에서 각 점 까지 의 최 단 로 를 dis [] 배열 로 저장 하 십시오.
그리고 A * 함수, F [x] = H [x] + G [x] 를 사용 합 니 다.
제목: POJ 2449
구체 적 인 설명 은 코드 안에 있다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int Maxn = 1e5 + 7;
const int Inf = 1e9 + 7;
int N , M , K;
int start , End;
int ans;
//
int dis[Maxn];
bool vis[Maxn];
struct node{
int v , w;
friend bool operator < (node a , node b){
return a.w > b.w;
}
};
/*
* A* F[x] = H[x] + G[x]
* Hx
* Gx （ ， ）
*/
struct edge{
int v , Hx , Gx;
friend bool operator < (edge a , edge b){
return a.Hx + a.Gx > b.Hx + b.Gx;
}
};
/*
* count BFS
* count == K （ K ）
*/
int Count[Maxn];
vector G[Maxn] , G2[Maxn];
/*
* （ ）
* End
*/
void Dijkstra(){
fill(vis , vis+N+1 , false);
fill(dis , dis+N+1 , Inf);
priority_queue que;
que.push((node){End , 0});
dis[End] = 0;
node q;
int v , w;
while(!que.empty()){
q = que.top(); que.pop();
v = q.v , w = q.w;
if(vis[v]) continue;
vis[v] = true;
int to_v , to_w;
for(int i = 0 ; i < G2[v].size() ; i++){
to_v = G2[v][i].v , to_w = G2[v][i].w + w;
if(dis[to_v] > to_w){
dis[to_v] = to_w;
que.push((node){to_v , to_w});
}
}
}
}
/*
* K = A* + BFS
*/
void Astar(){
ans = -1;
fill(Count , Count+N+1 , 0);
priority_queue que;
que.push((edge){start , 0 , 0});
edge q;
int v , Hx , Gx;
while(!que.empty()){
q = que.top(); que.pop();
v = q.v , Hx = q.Hx , Gx = q.Gx;
Count[v]++;
if(Count[v] == K && v == End){
ans = Hx + Gx;
break;
}
if(Count[v] > K) continue;
int to_v , to_hx , to_gx;
for(int i = 0 ; i < G[v].size() ; i++){
to_v = G[v][i].v;
to_hx = Hx + G[v][i].w;
to_gx = dis[to_v];
que.push((edge){to_v , to_hx , to_gx});
}
}
while(!que.empty()) que.pop();
return;
}
int main()
{
while(~scanf(" %d %d",&N,&M)){
for(int i = 1 ; i <= N ; i++) G[i].clear();
for(int i = 1 ; i <= M ; i++){
int u , v , w; scanf(" %d %d %d",&u,&v,&w);
G[u].push_back((node){v, w});
G2[v].push_back((node){u, w});
}
scanf(" %d %d %d",&start , &End , &K);
// start End 0 ， K++
if(start == End) K++;
Dijkstra();
Astar();
printf("%d
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전
Udemy 에서 공부 한 것을 중얼거린다
Chapter3【Integer Reversal】
(예)
문자열로 숫자를 반전 (toString, split, reverse, join)
인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
