emmm交了第8次才过。
这道题目测一道单源最短路问题，因此dijkstra或者spfa板子先准备好。因为题中对最短路有限定：
- 路径上的所有点的出边所指向的点都直接或间接与终点连通。
- 在满足条件1的情况下使路径最短。
而题中还说“题目保证终点没有出边。”，所以我们考虑反向处理，也就是说最短路径上的点一定在以终点为根的搜索树上，并且这些点的所有出边一定也在这棵树上。所以考虑dfs/bfs搜索图，标记所有搜过的点，然后枚举每个标记点的出边所指向的点，如果不在树上则删除标记。这里有一个坑点，如果直接对标记进行修改，由于树上的编号和搜索顺序没有关系，会导致改标记的时候把没扫到的点也改掉了，从而造成删掉不该删掉的点，因此考虑备份标记即可。
然后我错这么多次的原因，说起来非常水，原因是在spfa的时候没有对入队的元素标记，数据大的时候入队多次直接爆空间，只有第一个点数据小能水10分QAQ
参考代码：
#include<iostream>
#include<cstdio>
#include<queue>
#define N 10010
#define M 200010
#define inf 1e8
using namespace std;
queue<int>q;
int nxt[M],to[M],fnxt[M],fto[M];
int n,m,in_q[N],head[N],vis[N],fhead[N],fcnt,cnt,visited[N],dis[N],s,t;
void dfs(int x)
{
visited[x] = ;
for(int i = fhead[x];i;i = fnxt[i])
{
if(!visited[fto[i]]) dfs(fto[i]);
}
}
void spfa()
{
for(int i = ;i <= n;i++) dis[i] = inf;
in_q[s] = ;
dis[s] = ;
q.push(s);
int u;
while(!q.empty())
{
u = q.front();
q.pop();
in_q[u] = ;
if(!visited[u]) continue;
for(int i = head[u];i;i = nxt[i])
{
if(dis[to[i]] > dis[u] + )
{
dis[to[i]] = dis[u] + ;
if(!in_q[to[i]])
{
in_q[to[i]] = ;
q.push(to[i]);
}
}
}
}
}
void del()
{
for(int i = ;i <= n;i++) vis[i] = visited[i];
for(int i = ;i <= n;i++)
{
if(!vis[i])
{
for(int j = fhead[i];j;j = fnxt[j])
{
if(vis[fto[j]]) visited[fto[j]] = ;
}
}
}
} void add(int u,int v,int k)
{
if(k == )
{
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
else
{
fto[++fcnt] = v;
fnxt[fcnt] = fhead[u];
fhead[u] = fcnt;
}
return;
}
int main()
{
scanf("%d %d",&n,&m);
int u,v;
for (int i = ;i <= m;i++)
{
scanf("%d %d",&u,&v);
add(u,v,);
add(v,u,); }
scanf("%d %d",&s,&t);
dfs(t);
del();
spfa();
printf("%d",(dis[t] >= inf) ? - : dis[t]);
}