nyoj 三国志 (Dijkstra + 01背包)-白红宇的个人博客

发布日期：2021-06-24 06:57:19 浏览次数：4 分类：技术文章

本文共 1722 字，大约阅读时间需要 5 分钟。

。。。总是没思路真要命

注意两点之间可能有多条权值不同的路径，不过只要在输入时取最小值就好了。。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #include
                 
                  14 #include
                  
                   15 #include
                   
                    16 #define INF 1e717 #define MAXN 10001018 #define maxn 5019 #define maxm 100020 #define Mod 100000721 using namespace std;22 typedef long long LL;23 24 25 int T;26 int s, n, m;27 int a, b, c;28 int v[110];29 int G[110][110];30 int dist[1000010];31 int vis[110];32 int dp[1000010];33 34 void Dijkstra()35 {36 for (int i = 0; i <= n; ++i)37 dist[i] = G[0][i],vis[i] = 0;38 int pos, min;39 vis[0] = 1;40 dist[0] = 0;41 for (int i = 1; i <= n; ++i) {42 min = INF;43 for (int j = 1; j <= n; ++j) {44 if (!vis[j] && min > dist[j]) {45 pos = j;46 min = dist[j];47 }48 }49 vis[pos] = 1;50 for (int j = 1; j <= n; ++j) {51 if (!vis[j] && dist[j] > dist[pos] + G[pos][j])52 dist[j] = dist[pos] + G[pos][j];53 }54 }55 }56 57 void bag01()58 {59 for (int i = 1; i <= n; ++i)60 for (int j = s; j >= dist[i]; --j)61 dp[j] = max(dp[j - dist[i]] + v[i],dp[j]);62 }63 64 void run()65 {66 scanf("%d%d%d", &s, &n, &m);67 memset(v,0,sizeof(v));68 memset(dp,0,sizeof(dp));69 for (int i = 0; i <= n; ++i)70 for (int j = 0; j <= n; ++j)71 G[i][j] = INF;72 for (int i = 0; i < m; ++i) {73 scanf("%d%d%d", &a, &b, &c);74 if (c < G[a][b])75 G[a][b] = G[b][a] = c;76 }77 for (int i = 1; i <= n; ++i) 78 scanf("%d",&v[i]);79 Dijkstra();80 bag01();81 printf("%d\n",dp[s]);82 }83 int main()84 {85 scanf("%d", &T);86 while (T--)87 run();88 return 0;89 }

转载于:https://www.cnblogs.com/usedrosee/p/4337882.html

转载地址：https://blog.csdn.net/weixin_30896763/article/details/98599659 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：html基础——标签

下一篇：Open JDk 源码下载地址

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章