我自己优化了一下先排序，减少深搜时对边不必要的遍历，4、5过了但额外测试点还是过不了，求大佬帮忙
```
#include <iostream>
#include <queue>
#include <algorithm>
#include <stdio.h>
using namespace std;
struct edge
{
int a;
int b;
};
edge e[4000006];
int N;
int M;
int num[1000006] = { 0 };
int dist[1000006] = { 0 };
int Search[1000006];
queue<int>q;
void bfs()
{
q.push(1);
while (!q.empty())
{
int e1 = q.front();
q.pop();
for (int i = Search[e1]; e[i].a == e1; i++)
{
int e2 = e[i].b;
if (dist[e2] == 0 && e2 != 1)
{
dist[e2] = dist[e1] + 1;
q.push(e2);
num[e2] = (num[e2] + num[e1]) % 100003;
}
else if (dist[e2] == dist[e1] + 1)
{
num[e2] = (num[e2] + num[e1]) % 100003;
}
}
}
}
bool judge(edge m, edge n)
{
return m.a < n.a;
}
int main()
{
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int x, y;
cin >> x >> y;
e[i].a = x;
e[i].b = y;
e[i + M].a = y;
e[i + M].b = x;
}
sort(e, e + 2 * M, judge); //排序
int k = 0;
for (int i = 0; i < 2 * M; i++)
{
if (k != e[i].a) //记录某一边的起始点在数列中出现的位置
{
k = e[i].a;
Search[k] = i;
}
}
num[1] = 1;
dist[1] = 0;
bfs();
for (int i = 1; i <= N; i++)
{
cout << num[i] << endl;
}
return 0;
}
```
by AIBEYOND @ 2024-03-13 19:48:11
看到的第一眼，以为是深搜，第二眼，发现是 优化 $\text{dijstra}$ ，再看一眼，好像是 $\text{Bellman Ford}$ ，最后一眼，好像都不是。
@[AIBEYOND](/user/1042314) 只能说很有实力，真的相当有实力，我是看不出是什么常规算法了，你可能硬生生自造了一个算法。
然而正解当然不是这样的，规定**最短距离为当前点到起点的最短距离**，既然是广搜，那么从 1 点开始，当**第一次到达某个点的时候，那么这个点的最短距离已确定**，接下来只需要计数了，然而**已经确定最短距离的点就无需再加入队列了**，因为确定者已经更新过其相连点的最短距离，无需二次加入队列。
具体地讲，进了队列的，处理后，标记一下，只有未标记的才进队列，直到队列中再无他点，你将得到正确答案。
你最好模拟一下，自己造个数据，这将让你有更深的理解。
by DHWJHY @ 2024-03-22 20:42:49