C 언어 BFS (5)TT 와 마법사 (swustoj 2464)
TT , , “ ”! , 。 , A,B,C , A,B,C , , , , A A 。
,TT 1 N, , 1 N。 , 。 , , , , , , A->B->C->A….. 。 A。 TT 1 N 。 , , , 。
Input
T, 2 N,M N M (1<=N<=1000,0<=M<=N*N)。 M , S T L C(S!=T,1<=L<=1000,1<=C<=3) S T (1<=S,T<=N) L C ( , 1,2,3 A,B,C ) ( )。
Output
TT 1 N, , -1
Sample Input
2
4 3
1 2 1 1
2 3 2 2
3 4 3 3
4 3
1 2 1 1
2 3 2 2
3 4 3 2
Sample Output 6
-1
원본 링크:http://www.oj.swust.edu.cn/problem/show/2464
분석:
처음에 생각 했 던 것 은 기억 으로 검색 한 다음 에 무정 한 WA 의 여러 번 생각 했 습 니 다. 그 다음 에 랜 덤 으로 데 이 터 를 생 성하 고 AC 코드 와 비교 해서 달 릴 수 밖 에 없 었 습 니 다. 마침내 수천 개의 데 이 터 를 달 려 서 원인 을 찾 았 습 니 다. 기억 화 검색 은 이 문제 에서 발생 하 는 단점 은 경로 순서 로 문 제 를 읽 으 면 특정한 점 A 를 거 쳐 다른 점 B 에 도착 할 수 있 습 니 다. 만약 에 B 에서 A 까지 N 점 까지 의 경로 가 존재 한다 면이때 A 시 에 먼저 도 착 했 기 때문에 A 가 표 시 된 다음 에 B 는 A 를 통 해 N 시 에 도착 할 수 없 었 고 이때 B 의 데 이 터 는 종점 에 도달 할 수 없 는 것 으로 기억 되 었 다.그러나 표 시 는 취소 할 수 없 으 며, 그렇지 않 으 면 고리 모양 의 지도 에서 순환 할 것 이다.이 문 제 는 기억 화 검색 의 문제 중 하나 일 뿐 이지 만 코드 를 여러 번 바 꾼 것 은 Wa 입 니 다.
다음 에 기억 화 된 검색 코드 를 붙 입 니 다:#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <stdlib.h>
using namespace std;
int memory[1001][1001][4],n,m;
int mpt[1001][1001][4],money[1001][1001][4];
bool book[1001][1001][4];
vector<int>way[1001];
int Min(int a,int b){
return (a>b)? b:a;
}
int dfs(int pre,int step,int k){
if(step==n)return 0;
if(memory[pre][step][k])return memory[pre][step][k];
book[pre][step][k]=true;
int i,ans=999999999;
for(i=0;i<way[step].size();i++){
//cout<<step<<"→"<< way[step][i]<<endl;
//printf("book[%d][%d]=%d
",way[step][i],k%3+1,book[way[step][i]][k%3+1]);
if(mpt[step][way[step][i]][k]==0 || book[step][way[step][i]][k%3+1]==true)continue;
//cout<<step<<"→"<< way[step][i]<<" K:"<<k<<endl;
ans=Min(ans,dfs(step,way[step][i],k%3+1)+money[step][way[step][i]][k]);
}
book[pre][step][k]=false;
//printf("memort[%d][%d]=%d
",step,k,ans);
if(ans!=999999999)
memory[pre][step][k]=ans;
return ans;
}
void init(){
int i;
for(i=0;i<1001;i++) way[i].clear();
memset(memory,0,sizeof(memory));
memset(money,0,sizeof(money));
memset(mpt,0,sizeof(mpt));
memset(book,0,sizeof(book));
}
int main()
{
int i,j,v,u,k,w,t,ans;
cin>>t;
while(t--){
cin>>n>>m;
init();
for(i=0;i<m;i++){
scanf("%d%d%d%d",&v,&u,&w,&k);
if(mpt[v][u][1]==0 && mpt[v][u][2]==0 && mpt[v][u][3]==0){
way[v].push_back(u);
way[u].push_back(v);
}
if(money[v][u][k]==0) money[v][u][k]=w,money[u][v][k]=w;
else{
money[v][u][k]=Min(money[v][u][k],w);
money[u][v][k]=Min(money[u][v][k],w);
}
mpt[u][v][k]=mpt[v][u][k]=1;
}
ans=dfs(0,1,1);
if(ans!=999999999)printf("%d
",ans);
else printf("-1
");
}
return 0;
}
그리고 SPFA 로 이 문 제 를 풀 겠 습 니 다.#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <stdlib.h>
using namespace std;
struct node
{
int data,v,w;
};
struct node1
{
int step,v;
};
int n,m;
int visit[1001][4],dis[1001][4]; //visit [ ][ ] .
vector<node>mpt[1001];
void SPFA()
{
node1 s,e;
int i,j,ss;
queue<node1>team;
s.step=1;s.v=1;
team.push(s);
visit[1][1]=1;
while(team.size()){ // .
s=team.front();
team.pop();
visit[s.step][s.v]=0;
ss=mpt[s.step].size();
for(i=0;i<ss;i++){
if(mpt[s.step][i].v!=s.v)continue;
if(dis[s.step][s.v]+mpt[s.step][i].w>=dis[mpt[s.step][i].data][s.v%3+1])continue;
dis[mpt[s.step][i].data][s.v%3+1]=dis[s.step][s.v]+mpt[s.step][i].w; //
if(visit[mpt[s.step][i].data][s.v%3+1]!=0)continue;
e.step=mpt[s.step][i].data;
e.v=s.v%3+1;
visit[e.step][e.v]=1;
team.push(e);
}
}
int min=1999999999;
for(i=1;i<4;i++)if(min>dis[n][i])min=dis[n][i];
if(min!=1999999999)cout<<min<<endl;
else cout<<"-1"<<endl;
}
int main()
{
int i,j,t,x,y;
cin>>t;
while(t--){
cin>>n>>m;
memset(visit,0,sizeof(visit));
for(i=1;i<=n;i++)for(j=0;j<4;j++)dis[i][j]=1999999999;
dis[1][1]=0;
for(i=0;i<1001;i++)mpt[i].clear();
for(i=0;i<m;i++){
node s;
cin>>x>>y>>s.w>>s.v;
s.data=x;
mpt[y].push_back(s);
s.data=y;
mpt[x].push_back(s);
}
SPFA();
}
return 0;
}
만약 큰 신 이 기억 화 검색 으로 만 들 수 있다 면 아래 에 붙 여 주세요. 대단히 감사합니다!!!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.