利用dijkstra求解最短路计数出现问题

Question

利用dijkstra在枚举最短路的过程中顺便更新路径数
[原题链接]（https://www.luogu.com.cn/problem/P1144

用代码块功能插入代码，请勿粘贴截图

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

typedef long long LL;
const int N=1e6;
LL h[N],e[N],ne[N],w[N],idx;  // 邻接表存储
int n,m;  // n个顶点,m条边
LL dist[N]; // 每个点到1的距离
LL ans[N];  // 标记起点到每个点的路径条数
bool st[N];  // 标记是否在点集内

#define x first
#define y second
typedef pair<int,int>PII;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=1,h[a]=idx++;
}
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;ans[1]=1;
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,1});
    
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.y,distance=t.x;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])  // 比之前的距离小，到达该点的最短路径数修改为能到ver的数量
            {
                ans[j]=ans[ver];
                dist[j]=distance+w[i];
                heap.push({dist[j],j});
            }
          else if(dist[j]==dist[ver]+w[i]) ans[j]+=ans[ver];
        }
    }
}
int main()
{
   memset(h,-1,sizeof h);
   scanf("%d%d",&n,&m);
   while(m--)
   {
    int a,b;
    scanf("%d%d",&a,&b);
    add(a,b);add(b,a);
   }
   dijkstra();
   for(int i=1;i<=n;i++)
    cout<<ans[i]%100003<<endl;
   return 0;
}

运行结果及报错内容

我的解答思路

如果从起点到t有ans[t]条边，从t到j有x条边，那么从起点到j就有两者相乘条边，也可以相加x次，就是每找到一条从t到j的边就加ans[t]

Answer 1

• 这篇文章讲的很详细，请看：最短路之Dijkstra+堆优化（单源最短路）