[code=Cpp width=700px]#include <stdio.h>
#define M 1008
int f[1008], g[1008], p[1008];
int e[4000008][2], nx[4000008], head[1008], fre = 1;
int n;
int que[1008], tp, bt, in[1008];
void spfa()
{
int u, k;
bt = 0;
for (tp = 0;tp < n;tp++)
{
que[tp] = tp;
in[tp] = 1;
}
while (bt != tp)
{
u = que[bt++];
bt %= M;
for (k = head;k;k = nx[k])
if (f[ e[k][1] ] > f[ e[k][0] ] + f)
{
f[ e[k][1] ] = f[ e[k][0] ] + f;
if (in[ e[k][1] ] == 0)
{
que[tp++] = e[k][1];
tp %= M;
in[ e[k][1] ] = 1;
}
}
}
}
void ac(int u)
{
int i, k;
g = 0;
for (i = 0;i < n;i++)
for (k = head;k;k = nx[k])
if (f[ e[k][0] ] + f == f && e[k][1] == u)
{
ac(i);
ac(e[k][0]);
g += g[ e[k][0] ] * g;
}
g /= 2;
if (f == p)
g++;
}
int main()
{
freopen("syrup.in", "r", stdin);
freopen("syrup.out", "w", stdout);
int i, x, y, z;
scanf("%d", &n);
for (i = 0;i < n;i++)
{
scanf("%d", &f);
p = f;
}
while (scanf("%d %d %d", &x, &y, &z) != EOF)
{
e[fre][0] = y; e[fre][1] = z; nx[fre] = head[x]; head[x] = fre++;
e[fre][0] = x; e[fre][1] = z; nx[fre] = head[y]; head[y] = fre++;
}
spfa();
ac(0);
printf("%d %d\n", f[0], g[0]);
return 0;
}
[/code]
|