nyoj 203 三国志 dijkstra+01背包

题目链接: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;
}



上一篇:NHibernate入门


下一篇:hdu 3339 In Action (最短路径+01背包)