社区讨论
求助大佬,有关变量大小
学术版参与者 4已保存回复 14
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 14 条
- 当前快照
- 1 份
- 快照标识符
- @mi4reb1d
- 此快照首次捕获于
- 2025/11/18 23:59 3 个月前
- 此快照最后确认于
- 2025/11/20 04:26 3 个月前
求助大佬,改了2小时都没发现哪里爆int了
WA 20pts:
CPP#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pa pair<int,ll>
const int N=3e5+5,M=7e5+5,K=250005;
const ll inf=1e18;
int id,n,m,k,len,v[K],w[K],a,b,c,g[N],fir[N],bel[M],vis[M];
ll ans[N],sum[K],dis[M],d;
vector<pa>Q[N],s[M],t[M];
priority_queue<pa,vector<pa>,greater<pa>>q;
int main(){
scanf("%d%d%d%d",&id,&n,&m,&k);
for(int i=1;i<k;i++) scanf("%d",&v[i]);
for(int i=2;i<=k;i++) scanf("%d",&w[i]),sum[i]=sum[i-1]+w[i];
len=n;for(int i=1;i<=n;i++){
scanf("%d",&g[i]);fir[i]=len;
for(int j=1;j<=g[i];j++){
bel[++len]=i;scanf("%d%d",&b,&c);Q[i].push_back({b,c});
if(j<g[i]) s[len].push_back({len+1,v[j]});
if(j>1) s[len].push_back({len-1,w[j]});
}ans[i]=inf;bel[i]=i;
}for(int i=1;i<=n;i++){
k=0;for(pa j:Q[i]){
t[fir[i]+(++k)].push_back({b=j.first,c=j.second});
if(k<=g[b]) s[fir[i]+k].push_back({fir[b]+k,c});
else if(g[b]) s[fir[i]+k].push_back({fir[b]+g[b],sum[k]-sum[g[b]]+c});
}
}for(int i=1;i<=len;i++) dis[i]=inf;
if(g[1]) q.push({dis[n+1]=0,n+1});ans[1]=0;
while(!q.empty()){
a=q.top().second;q.pop();
if(vis[a]++) continue;
for(pa i:s[a]) if(dis[a]+(d=i.second)<dis[b=i.first]) q.push({dis[b]=dis[a]+d,b});
for(pa i:t[a]) ans[bel[i.first]]=min(ans[bel[i.first]],dis[a]+i.second);
}for(int i=1;i<=n;i++) printf("%lld ",(ans[i]==inf?-1ll:ans[i]));
return 0;}
AC:
CPP#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pa pair<ll,ll>
const ll N=3e5+5,M=7e5+5,K=250005;
const ll inf=1e18;
ll id,n,m,k,len,v[K],w[K],a,b,c,g[N],fir[N],bel[M],vis[M];
ll ans[N],sum[K],dis[M],d;
vector<pa>Q[N],s[M],t[M];
priority_queue<pa,vector<pa>,greater<pa>>q;
int main(){
scanf("%lld%lld%lld%lld",&id,&n,&m,&k);
for(ll i=1;i<k;i++) scanf("%lld",&v[i]);
for(ll i=2;i<=k;i++) scanf("%lld",&w[i]),sum[i]=sum[i-1]+w[i];
len=n;for(ll i=1;i<=n;i++){
scanf("%lld",&g[i]);fir[i]=len;
for(ll j=1;j<=g[i];j++){
bel[++len]=i;scanf("%lld%lld",&b,&c);Q[i].push_back({b,c});
if(j<g[i]) s[len].push_back({len+1,v[j]});
if(j>1) s[len].push_back({len-1,w[j]});
}ans[i]=inf;bel[i]=i;
}for(ll i=1;i<=n;i++){
k=0;for(pa j:Q[i]){
t[fir[i]+(++k)].push_back({b=j.first,c=j.second});
if(k<=g[b]) s[fir[i]+k].push_back({fir[b]+k,c});
else if(g[b]) s[fir[i]+k].push_back({fir[b]+g[b],sum[k]-sum[g[b]]+c});
}
}for(ll i=1;i<=len;i++) dis[i]=inf;
if(g[1]) q.push({dis[n+1]=0,n+1});ans[1]=0;
while(!q.empty()){
a=q.top().second;q.pop();
if(vis[a]++) continue;
for(pa i:s[a]) if(dis[a]+(d=i.second)<dis[b=i.first]) q.push({dis[b]=dis[a]+d,b});
for(pa i:t[a]) ans[bel[i.first]]=min(ans[bel[i.first]],dis[a]+i.second);
}for(ll i=1;i<=n;i++) printf("%lld ",(ans[i]==inf?-1ll:ans[i]));
return 0;}
P13271 [NOI2025] 机器人
对于所有测试数据,保证:
- ,;
- 对于所有 ,均有 ;
- 对于所有 ,均有 ;
- 对于所有 ,均有 ,且 ;
- 对于所有 ,,均有 ,。
回复
共 14 条回复,欢迎继续交流。
正在加载回复...