终于Ａ了
看这题容易想到最短路 看到错的很多 还特意注意了好几处
后来发现 必须按给出的顺序出边 想了想 这不就是ＢＦＳ
然后就是各种细节 ｉ－＞ｉ＋１ｏｒｉ－＞ｊ（ａ［ｉ］＝＝ａ［ｊ］）
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<vector>
using namespace std;
#define N 10010
#define INF 0xfffffff
vector<int>ed[N];
vector<int>::iterator it;
int vis[N*],pa[N*],a[N*],o[N*],f[N*];
int n,ff[N*];
struct node
{
int x,num;
};
void bfs(int s,int e)
{
int i,oo,minz = INF;
queue<node>q;
node st,te;
st.x = s;
st.num = ;
pa[s] = s;
q.push(st);
while(!q.empty())
{
te = q.front();
int u = te.x;
q.pop();
if(te.num>minz)
continue;
if(a[u]==e)
{
minz = te.num;
oo = u;
continue;
}
if(ff[u]&&!vis[ff[u]])
{
int v = ff[u];
if(!vis[v])
{
vis[v] = ;
st.x = v;
st.num = te.num;
q.push(st);
pa[v] = pa[u];
}
}
if(!vis[u+]&&u<n)
{
vis[u+] = ;
st.x = u+;
st.num = te.num+;
q.push(st);
pa[u+] = u;
}
}
int x = oo,g=;
o[g++] = a[oo];
while(x!=s)
{
x = pa[x];
o[g++] = a[x];
}
for(i = g- ; i >= ; i--)
if(o[i]!=o[i+])
printf("%d ",o[i]);
puts("");
}
int main()
{
int i;
scanf("%d",&n);
for(i =; i <= n ; i++)
{
scanf("%d",&a[i]);
if(f[a[i]])
{
ff[f[a[i]]] = i;
f[a[i]] = i;
}
else
f[a[i]] = i;
}
bfs(,a[n]);
return ;
}