AcWing 1011. 挖地雷
原题链接
简单
作者:
一块两毛五
,
2024-03-30 18:57:36
,
所有人可见
,
阅读 2
#include <iostream>
using namespace std;
const int N = 210;
long long f[N];
int n;
long long a[N][N];
long long w[N];
long long res;
int pre[N];
int pos;
void dfs(int x)
{
if(pre[x])
dfs(pre[x]);
if(x == pos)
cout << x;
else
cout << x << "-";
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> w[i];
f[i] = w[i];
}
int x, y;
while(cin >> x >> y, x || y)
{
a[x][y] = 1;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j < i; j++)
{
if(a[j][i] && f[i] < f[j] + w[i])
{
f[i] = f[j] + w[i];
pre[i] = j;
}
}
if(res < f[i])
{
res = f[i];
pos = i;
}
}
dfs(pos);
cout << endl;
cout << res;
return 0;
}