30求条
查看原帖
30求条
1187632
Y75C楼主2025/7/19 15:36

只过了点1-2和点9-12

#include<bits/stdc++.h>;
using namespace std;
const int mx=3e5+7;
typedef long long ll;
#define pa pair<ll,pair<int,int> >//val dot p;
#define sec second
#define fir first
int c,n,m,k;
int v[mx],w[mx],d[mx];ll sv[mx],sw[mx];
ll val[mx];
vector<pair<int,int> > vmp[mx];
priority_queue<pa,vector<pa>,greater<pa> > qu;
ll pbh(int l,int r){
  if(l>r) return sw[l]-sw[r];
  else return sv[r-1]-sv[l-1];
}
void dijkstra(){
  qu.push({0,{1,1}});
  memset(val,0x3f,sizeof(val));
  val[1]=0;
  while(qu.size()){
    ll vl=qu.top().fir;int dot=qu.top().sec.fir,p=qu.top().sec.sec;
    qu.pop();
    for(int i=0;i<vmp[dot].size();i++){[i].fir,pbh(p,i+1),vl+vmp[dot][i].fir+pbh(p,i+1),val[vmp[dot][i].sec]);
      if(1ll*vl+vmp[dot][i].fir+pbh(p,i+1)<val[vmp[dot][i].sec]){
        val[vmp[dot][i].sec]=1ll*vl+vmp[dot][i].fir+pbh(p,i+1);
        qu.push( { val[vmp[dot][i].sec] , { vmp[dot][i].sec , i+1 } } );
      }
    }
  }
}
int main(){
  scanf("%d%d%d%d",&c,&n,&m,&k);
  for(int i=1;i<=k-1;i++){scanf("%d",&v[i]);sv[i]=sv[i-1]+v[i];}
  for(int i=2;i<=k;i++){scanf("%d",&w[i]);sw[i]=sw[i-1]+w[i];}
  for(int i=1;i<=n;i++){
    scanf("%d",&d[i]);
    for(int j=1;j<=d[i];j++){
      int y,z;
      scanf("%d%d",&y,&z);
      vmp[i].push_back({z,y});
    }
  }
  dijkstra();
  for(int i=1;i<=n;i++){
    if(val[i]==0x3f3f3f3f3f3f3f3f) printf("-1 ");
    else printf("%lld ",val[i]);
  }
  return 0;
}
2025/7/19 15:36
加载中...