题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=203

思路：先求点0到每个点的最短距离，dijkstra算法，然后就是01背包了

我奇怪的是100*1000000的时间复杂度居然没有超时！

代码如下：

#include "stdio.h"

#include "string.h"

#define N 105

#define INF 0x3fffffff

bool mark[N];

int dist[N];

int map[N][N];

int dp[1000005];

void Init(int n)

{

    for(int i=0; i<=n; ++i)

    {

        for(int j=0; j<=n; ++j)

            map[i][j] = INF;

    }

}

void dij(int n)

{

    int i,j,k;

    memset(mark,false,sizeof(mark));

    for(i=0; i<=n; ++i)

        dist[i] = map[0][i];

    mark[0] = true;

    int mint;

    for(i=1; i<=n; ++i)

    {

        k = 0;

        mint = INF;

        for(j=0; j<=n; ++j)

        {

            if(!mark[j] && mint>dist[j])

            {

                mint = dist[j];

                k = j;

            }

        }

        mark[k] = true;

        for(j=0; j<=n; ++j)

        {

            if(!mark[j] && dist[j]>dist[k]+map[k][j])

                dist[j] = dist[k]+map[k][j];

        }

    }

}

int value[N];

int main()

{

    int T;

    int n,sum,m;

    int i,j;

    int x,y,k;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d %d %d",&sum,&n,&m);

        Init(n);

        while(m--)

        {

            scanf("%d %d %d",&x,&y,&k);

            if(k<map[x][y])

                map[x][y] = map[y][x] = k;

        }

        for(i=1; i<=n; ++i)

            scanf("%d",&value[i]);

        dij(n);

        memset(dp,0,sizeof(dp));

        for(i=1; i<=n; ++i)  //01背包

        {

            for(j=sum; j>=dist[i]; j--)

            {

                if(dp[j] < dp[j-dist[i]] + value[i])

                    dp[j] = dp[j-dist[i]]+value[i];

            }

        }

        int ans = 0;

        for(i=1; i<=sum; ++i)

            ans = ans>dp[i]?ans:dp[i];

        printf("%d\n",ans);

    }

    return 0;

}