标签：val int long 400005 Skipping push n1
- 【知难而退】，难以实时维护一个位置对应的下一个位置，那就通过一定的性质避开这个问题
- 【枚举】到达的最右边的位置
- 真没想到在这种特殊图上也能卡spfa啊……
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[400005];
vector<int>c[400005];
int val[400005],b[400005];
long long sum[400005],d[400005];
bool v[400005];
/*
queue<int>q;
void spfa()
{
d[1]=0;
v[1]=true;
q.push(1);
while(q.size())
{
int n1=q.front();
q.pop();
v[n1]=false;
for(int i=0;i<a[n1].size();i++)
{
if(d[n1]+c[n1][i]<d[a[n1][i]])
{
d[a[n1][i]]=d[n1]+c[n1][i];
if(!v[a[n1][i]])
{
v[a[n1][i]]=true;
q.push(a[n1][i]);
}
}
}
}
}
*/
typedef pair<long long,int> cc;
priority_queue<cc,vector<cc>,greater<cc> >q;
void dijkstra()
{
d[1]=0;
q.push(make_pair(0,1));
while(q.size())
{
int n1=q.top().second;
q.pop();
if(v[n1])
{
continue;
}
v[n1]=true;
for(int i=0;i<a[n1].size();i++)
{
if(d[n1]+c[n1][i]<d[a[n1][i]])
{
d[a[n1][i]]=d[n1]+c[n1][i];
q.push(make_pair(d[a[n1][i]],a[n1][i]));
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
a[i].clear();
c[i].clear();
d[i]=LLONG_MAX;
v[i]=false;
}
for(int i=1;i<=n;i++)
{
cin>>val[i];
sum[i]=sum[i-1]+val[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
if(i>1)
{
a[i].push_back(i-1);
c[i].push_back(0);
}
a[i].push_back(b[i]);
c[i].push_back(val[i]);
}
dijkstra();
long long ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,sum[i]-d[i]);
}
cout<<ans<<"\n";
}
return 0;
}
标签：val,
int,
long,
400005,
Skipping,
push,
n1
From： https://www.cnblogs.com/watersail/p/18494557