这个提示一个简单的最短路计数，除了用数组存上最短路的个数的做法以外，还有可以在得出最短路之后，搜索加剪枝的方法来通过该题。
可以反向搜索用A*的方法来通过，但是这个题的去重十分的恶心，需要一些玄学操作。
\(Code\)
// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstdlib>
using namespace std;
struct cym {
int to, len, nex;
}e[6000010], ed[6000010];
int lin[100100], lind[100100], vis[100100], dis[100100], dist[100100], map[2010][2010], n, m, minn = 2147483647, ans, cnt;
inline void add(int f, int t, int l)
{
e[++cnt].to = t;
e[cnt].len = l;
e[cnt].nex = lin[f];
lin[f] = cnt;
ed[cnt].to = f;
ed[cnt].len = l;
ed[cnt].nex = lind[t];
lind[t] = cnt;
}
void dfs(int now, int sum)
{
if (now == n && sum == minn)
{
ans++;
return;
}
if (now == n || dist[now] + sum > minn)
return;
if (sum >= minn) return;
for (int i = lin[now]; i; i = e[i].nex)
{
dfs(e[i].to, sum + e[i].len);
}
}
inline void spfa()
{
queue <int> q;
for (int i = 2; i <= n; i++)
dis[i] = 2147483647;
dis[1] = 0;
q.push(1);
while (!q.empty())
{
int cur = q.front();
q.pop(), vis[cur] = 0;
for (int i = lin[cur]; i; i = e[i].nex)
{
int to = e[i].to;
if (dis[cur] + e[i].len < dis[to])
{
dis[to] = dis[cur] + e[i].len;
if (!vis[to])
vis[to] = 1, q.push(to);
}
}
}
}
inline void spfad()
{
memset(vis, 0, sizeof(vis));
queue <int> q;
for (int i = 1; i <= n; i++)
dist[i] = 2147483647;
dist[n] = 0;
q.push(n);
while (!q.empty())
{
int cur = q.front();
q.pop(), vis[cur] = 0;
for (int i = lind[cur]; i; i = ed[i].nex)
{
int to = ed[i].to;
if (dist[cur] + ed[i].len < dist[to])
{
dist[to] = dist[cur] + ed[i].len;
if (!vis[to])
vis[to] = 1, q.push(to);
}
}
}
}
int main()
{
// freopen("hh.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (map[a][b] == 0)
map[a][b] = 214746;
if (map[a][b] <= c) continue;
add(a, b, c);
map[a][b] = c;
}
spfa();
spfad();
/*for (int i = 1; i <= n; i++)
{
printf("%d ", dist[i]);
}
return 0;*/
minn = dis[n];
dfs(1, 0);
if (m == 0 || minn == 2147483647)
printf("No answer"), exit(0);
printf("%d %d", minn, ans);
}