第一行输入三个正整数n,m，K，表示有n个点m条边，要求的路径需要经过K个点。接下来输入m行，每行三个正整数Ai,Bi,Ci(1<=Ai,Bi<=n,1<=Ci<=10000)，表示Ai和Bi间有一条长度为Ci的边。数据保证输入的是连通的无向图。

输出一行两个整数，以一个空格隔开，第一个整数表示包含K个点的路径最长为多长，第二个整数表示这样的不同的最长路径有多少条。

6 6 41 2 12 3 13 4 12 5 13 6 15 6 1

3 4

#include <iostream>#include <cstdio>#include <cstdlib>#include <cctype>#include <cstring>#include <algorithm>#include <queue>#include <vector>using namespace std;int read() {	int x = 0, f = 1; char c = getchar();	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }	return x * f;}#define maxn 30010#define maxm 60010#define oo 2147483647int n, m, M, K;struct Edge {	int v, w;	Edge() {}	Edge(int _, int __): v(_), w(__) {}	bool operator < (const Edge& t) const { return v < t.v; }} ;vector <Edge> E[maxn];bool vis[maxn];int d[maxn], fa[maxn], fad[maxn];struct Node {	int u, d;	Node() {}	Node(int _, int __): u(_), d(__) {}	bool operator < (const Node& t) const { return d > t.d; }} ;priority_queue <Node> Q;void Dijkstra() {	for(int i = 1; i <= n; i++) d[i] = oo;	d[1] = 0;	Q.push(Node(1, 0));	while(!Q.empty()) {		int u = Q.top().u; Q.pop();		if(vis[u]) continue;		vis[u] = 1;		for(int i = 0; i < E[u].size(); i++)			if(d[E[u][i].v] > d[u] + E[u][i].w) {				d[E[u][i].v] = d[u] + E[u][i].w;				fa[E[u][i].v] = u; fad[E[u][i].v] = E[u][i].w;				if(!vis[E[u][i].v]) Q.push(Node(E[u][i].v, d[E[u][i].v]));			}	}	return ;}int head[maxn], to[maxm], next[maxm], dist[maxm];void AddEdge(int a, int b, int c) {	to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;	swap(a, b);	to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;	return ;}int root, size, siz[maxn], f[maxn], ans, ansc;void getroot(int u, int pa) {	siz[u] = 1; f[u] = 0;	for(int e = head[u]; e; e = next[e]) if(!vis[to[e]] && to[e] != pa) {		getroot(to[e], u);		siz[u] += siz[to[e]];		f[u] = max(f[u], siz[to[e]]);	}	f[u] = max(f[u], size - siz[u]);	if(f[u] < f[root]) root = u;	return ;}int A[maxn], Ac[maxn], B[maxn], Bc[maxn], mxd;void dfs(int u, int d, int dep, int pa) {	mxd = max(mxd, dep);//	printf("XXX: %d %d %d\n", u, d, dep);	if(!Ac[dep] || A[dep] < d) A[dep] = d, Ac[dep] = 1;	else if(A[dep] == d) Ac[dep]++;	for(int e = head[u]; e; e = next[e]) if(!vis[to[e]] && to[e] != pa)		dfs(to[e], d + dist[e], dep + 1, u);	return ;}void solve(int u) {//	printf("u: %d\n", u);	vis[u] = 1;	int Mxd = 0;	for(int e = head[u]; e; e = next[e]) if(!vis[to[e]]) {		mxd = 0;		dfs(to[e], dist[e], 1, u);		Mxd = max(Mxd, mxd);		Ac[0] = Bc[0] = 1;//		for(int i = 1; i <= mxd; i++) printf("here: %d(%d) ", A[i], Ac[i]); putchar(‘\n‘);		for(int i = 1; i <= min(K, mxd); i++)			if(!ansc || ans < A[i] + B[K-i]) ans = A[i] + B[K-i], ansc = Ac[i] * Bc[K-i];			else if(ans == A[i] + B[K-i]) ansc += Ac[i] * Bc[K-i];		for(int i = 1; i <= mxd; i++) {			if(!Bc[i] || B[i] < A[i]) B[i] = A[i], Bc[i] = Ac[i];			else if(B[i] == A[i]) Bc[i] += Ac[i];			A[i] = Ac[i] = 0;		}	}	for(int i = 1; i <= Mxd; i++) B[i] = Bc[i] = 0;	for(int e = head[u]; e; e = next[e]) if(!vis[to[e]]) {		root = 0; f[0] = n + 1; size = siz[u]; getroot(to[e], u);		solve(root);	}	return ;}int main() {	n = read(); M = read(); K = read() - 1;	for(int i = 1; i <= M; i++) {		int a = read(), b = read(), c = read();		E[a].push_back(Edge(b, c)); E[b].push_back(Edge(a, c));	}	for(int i = 1; i <= n; i++) sort(E[i].begin(), E[i].end());		Dijkstra();	for(int i = 2; i <= n; i++) AddEdge(i, fa[i], fad[i]);//	for(int i = 1; i <= n; i++) printf("%d ", fa[i]); putchar(‘\n‘);	memset(vis, 0, sizeof(vis));	root = 0; f[0] = n + 1; size = n; getroot(1, 0);	solve(root);		printf("%d %d\n", ans, ansc);		return 0;}