2/4 最短路刷题(P1144,1186,2176)

https://www.luogu.com.cn/problem/P1144 最短路计数：输出从结点1开始到各个点的路径数。 用到了dp记录方案的的思想：本题核心代码

		for(int i=head[u];~i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(dist[v]>dist[u]+e[i].dis)    //更新最小路径数
            {
                dist[v]=dist[u]+e[i].dis;
                ans[v]=ans[u];    			//若只是大于，本质上还是一条路径，只是长度加1
                q.push(node{v,dist[v]});
            }
            else if(dist[v]==dist[u]+e[i].dis)
            {
                ans[v]+=ans[u];     //由于到这个点的长度相等，那么到v的方案数就要加上到u的方案数
                ans[v]%=mod;
            }
        }

完整代码：

#include

using namespace std;
const int maxn=1000005;
const int mod=100003;
const int inf=0x3f3f3f3f;
int n,m,head[maxn],cnt,dist[maxn],t,ans[maxn];
bool vis[maxn];
struct edge
{
    int to,dis,nxt;
}e[maxn];
void add_edge(int from,int to,int dis)
{
    e[++cnt].to=to;
    e[cnt].dis=dis;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
struct node
{
    int pos,dis;
    bool operator