作业 三国志

#include<stdio.h> 
#include<stdio.h> 
int load[109][109]; 
int v[109]; 
bool used[109]; 
int food[109][109]; 
int dist[109]; 
int ans[1000099]; 
int inf=99999; 
int minx(int a,int b) 
{ 
    if(a<b) 
        return a; 
    return b; 
} 
void Dijkstra(int n) 
{ 
    int i,j; 
    int q; 
    int min; 
    int loc=0; 
    used[0]=1; 
    dist[0]=0; 
    i=n+1; 
    for(j=1;j<=n;j++)//初始化 
    {dist[j]=inf+1;used[j]=0;} 
    while(i--) 
    { 
        min=inf; 
        for(j=0;j<=n;j++) 
        {//找新加入点 
            if(!used[j]&&min>dist[j]) 
            { 
                min=dist[j];loc=j; 
            } 
        } 
        used[loc]=1; 
        for(j=1;j<=load[loc][0];j++) 
        {//更新路径 
            q=load[loc][j]; 
            if(!used[q]) 
            {dist[q]=minx(dist[q],dist[loc]+food[loc][q]);} 
        } 
    } 
//  for(i=1;i<=n;i++) 
//      printf("%d ",dist[i]); 
} 
void _01backpack(int n,int s) 
{ 
    int i,j; 
    for(i=0;i<=s;i++) 
        ans[i]=0; 
    for(i=1;i<=n;i++) 
    { 
        for(j=s;j>=dist[i];j--)//注意只能是从S->0 不能是0->s 
        { 
                 
            if(ans[j]<ans[j-dist[i]]+v[i]) 
                ans[j]=ans[j-dist[i]]+v[i]; 
        } 
    } 
    printf("%d\n",ans[s]); 
} 
int main() 
{ 
    int T; 
    int s,n,m; 
    int i,j; 
    int a,b,c; 
    int q; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%d%d%d",&s,&n,&m); 
        for(i=0;i<=n;i++) 
        { 
            load[i][0]=0; 
            for(j=0;j<=n;j++) 
                food[i][j]=0; 
        } 
        for(i=0;i<m;i++) 
        { 
            scanf("%d%d%d",&a,&b,&c); 
            if(food[a][b]==0||food[a][b]>c)//因为可能有重边，所以取权最小的边 
            {//建立邻接表 
            q=++load[a][0];load[a][q]=b; 
            q=++load[b][0];load[b][q]=a; 
            food[a][b]=food[b][a]=c; 
            } 
        } 
        for(i=1;i<=n;i++) 
        {scanf("%d",&j);v[i]=j;} 
        Dijkstra(n); 
         _01backpack(n,s); 
    } 
    return 0; 
}