用dijkstra的思想，每次找药价的最小值，然后更新……

dijkstra秒杀
评测结果
编译成功

foo.cpp: In function 'void dijkstra(int)':
foo.cpp:27:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wparentheses]
if (!s[i] && v[k][i] < n+1)
^
测试数据 #0: Accepted, time = 0 ms, mem = 4432 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 4436 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 4436 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 4432 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 4436 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 4432 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 4436 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 4436 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 4436 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 4436 KiB, score = 10
Accepted, time = 92 ms, mem = 4436 KiB, score = 100
代码
#include <cstdio>
using namespace std;
const int INF = 0xfffff,maxn = 1001;
int n,dist[maxn],v[maxn][maxn],t[maxn];
bool s[maxn];
void input()
{
  scanf("%d",&n);
  for (int i = 0;i < n;i++)
    scanf("%d",&dist[i]);
  for (int i = 0;i < n;i++)
  {
    for (int j = 0;j < n;j++)
      v[i][j] = n+1;
    t[i] = s[i] = 1;
  }
  int a,b,c;
  while (scanf("%d%d%d",&a,&b,&c) == 3)
  {
    v[a][b] = c;
    v[b][a] = v[a][b];
  }
}
void dijkstra(int k)
{
  for (int i = 0;i < n;i++)
    if (!s[i] && v[k][i] < n+1)
      if (dist[v[k][i]] > dist[k]+dist[i])
      {
        dist[v[k][i]] = dist[k]+dist[i];
        t[v[k][i]] = t[k]*t[i];
      }
    else if (dist[v[k][i]] == dist[k]+dist[i])
      t[v[k][i]] += t[k]*t[i];
}
void work()
{
  for (int i = 0;i < n;i++)
  {
    int m = INF,k;
    for (int j = 0;j < n;j++)
      if (s[j] && dist[j] < m)
      {
        m = dist[j];
        k = j;
      }
    if(m == INF) break;
    s[k] = false;
    dijkstra(k);
 }
}
void output()
{
  printf("%d %d",dist[0],t[0]);
}
int main()
{
  input();
  work();
  output();
  return 0;
}

谁说树形dp不行只能用dijkstra！！！

前向星+树形dp秒杀！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

http://hi.baidu.com/shuai%5Fcannot/blog/item/e047b4fea919fd88b901a019.html

水题。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

90分的把邻接表开大点=AC