挖地雷（类似数塔）

题目描述

输入

第一行一个整数n表示有n个地窖

第二行有n个整数表示每个地窖的地雷数

以下有若干行，每行有两个数x,y表示x可以到y，保证x小于y。

最后一行有两个0，表示输入结束

输出

第一行输出挖地雷的顺序。

第二行为最多挖出的地雷数

样例输入

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

样例输出

3-4-5-6
34

提示

#include
#include<string.h>
#include<string>
#include
#include<string.h>
#include
#include
using namespace std;
int a[205];
int dp[205];
int f[205];
vector<int>v[205];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];f[i]=i;dp[i]=a[i];while(v[i].size()>0) v[i].pop_back();}int x,y;while(cin>>x>>y){if(x==0&&y==0) break;v[x].push_back(y);//x能到达的所有点记录
    }for(int i=n-1;i>=1;i--)//倒着遍历，类似数塔
    {for(int j=0;j){if(a[i]+dp[v[i][j]]>dp[i]){dp[i]=a[i]+dp[v[i][j]];f[i]=v[i][j];//通过f来记录路径
            }}}int mx=0;int k=-1;for(int i=1;i<=n;i++)//输出路径
    {if(dp[i]>mx){mx=dp[i];k=i;}}cout<<k;while(f[k]!=k){k=f[k];cout<<"-"<<k;}cout<<endl;cout<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！