1. 题目

传送门＝￣ω￣＝

2. 题解

同 https://www.mina.moe/?p=1227
跑一遍 spfa 再跑记忆化搜索。
至于什么情况下存在无限条最短路。。。
其实就是最短路径上存在一条边的花费为 0，那就可以来回走。。。就有无线条了。。。

所以直接在记忆话搜索的时候判断路径花费是否为 0 就行了。
如果为 0，输出-1 然后 exit(0)。
exit 函数可以直接退出程序，在 cstdlib 库里。

代码：

#include <bits/stdc++.h>
using namespace std;
static const int s=2005;
int n,m,head[s],to[s<<1],nxt[s<<1],w[s<<1],gsize,dis[s],ans[s];
bool book[s];
queue<int> que;
void adde(int u,int v,int k)
{
    to[gsize]=v,nxt[gsize]=head[u],w[gsize]=k,head[u]=gsize++;
}
int dfs(int u)
{
    if(ans[u])return ans[u];
    for(int i=head[u];i!=-1;i=nxt[i])
        if(dis[to[i]]+w[i]==dis[u])
        {
            if(w[i]==0)printf("-1\n"),exit(0);
            ans[u]=(ans[u]+dfs(to[i]))%1000000009;
        }
    return ans[u];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)head[i]=-1,dis[i]=INT_MAX;
    for(int i=1,u,v,k;i<=m;i++)scanf("%d%d%d",&u,&v,&k),adde(u,v,k),adde(v,u,k);
    dis[1]=0,que.push(1),book[1]=1;
    while(!que.empty())
    {
        int f=que.front();que.pop(),book[f]=0;
        for(int i=head[f];i!=-1;i=nxt[i])
            if(dis[f]+w[i]<dis[to[i]])
            {
                dis[to[i]]=dis[f]+w[i];
                if(!book[to[i]])que.push(to[i]),book[to[i]]=1;
            }
    }
    ans[1]=1,printf("%d\n",dfs(n));
    return 0;
}