题目

这个提示一个简单的最短路计数，除了用数组存上最短路的个数的做法以外，还有可以在得出最短路之后，搜索加剪枝的方法来通过该题。

可以反向搜索用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);

}