萌新:逃离僵尸岛

P3393 逃离僵尸岛

define int long long后仍然不行: ``` #include<bits/stdc++.h> #define int long long using namespace std; int n,m,k,s,p,q,num[100010],x,y,dis[100010]; bool c[100010],d[100010],vis[100010]; struct node{ int q,s; }; vector<node> a[100010]; queue<int> qt; void SPFA(int u){ for(int i=0;i<=n;i++){ dis[i]=1e9; vis[i]=0; } dis[u]=0; vis[u]=1; qt.push(u); while(!qt.empty()){ int now=qt.front(); vis[now]=0; for(int i=0;i<num[now];i++){ if(dis[a[now][i].q]>dis[now]+a[now][i].s){ dis[a[now][i].q]=dis[now]+a[now][i].s; if(!vis[a[now][i].q]){ vis[a[now][i].q]=1; qt.push(a[now][i].q); } } } qt.pop(); } } main(){ scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&s,&p,&q); while(k--){ scanf("%lld",&x); c[x]=1; } while(m--){ scanf("%lld%lld",&x,&y); if(c[x]&&c[y]) continue; if(c[x]) x=0; if(c[y]) y=0; a[x].push_back({y,1}); a[y].push_back({x,1}); num[x]++; num[y]++; } SPFA(0); for(int i=1;i<=n;i++){ if(dis[i]<=s) d[i]=1; } for(int i=1;i<=n;i++){ for(int j=0;j<num[i];j++){ if(a[i][j].q==n) a[i][j].s=0; else if(c[i]||c[a[i][j].q]) a[i][j].s=1e9; else if(d[i]||d[a[i][j].q]) a[i][j].s=q; else a[i][j].s=p; } } SPFA(1); printf("%lld",dis[n]); return 0; }
by YuRuochen @ 2022-08-25 21:24:51


### 这样试试 ```#include<bits/stdc++.h> using namespace std; const int N=100010; const long long inf=214748364701; queue <int> q; int n,m,k,ss,P,Q; long long dis[N],w[N<<2]; int s[N<<2][2],o[N],cnt; bool ocp[N],vis[N],dgs[N]; inline void add(int,int); inline void spfa(int now) { memset(vis,0,sizeof(vis)); for (int i=1;i<=n;++i) dis[i]=inf; while (!q.empty()) q.pop(); q.push(now);dis[now]=0;vis[now]=1; while (!q.empty()) { int x=q.front(); for (int i=o[x];i;i=s[i][1]) { int y=s[i][0]; if (dis[y]>dis[x]+w[i]) { dis[y]=dis[x]+w[i]; if (!vis[y]) vis[y]=1,q.push(y); } } vis[x]=0;q.pop(); } } int main() { ios::sync_with_stdio(false); cin>>n>>m>>k>>ss>>P>>Q; int x,y; for (int i=1;i<=k;++i) cin>>x,ocp[x]=1; for (int i=1;i<=m;++i) { cin>>x>>y; if (ocp[x]&&ocp[y]) continue; if (ocp[x]) add(0,y),add(y,0); else if (ocp[y]) add(0,x),add(x,0); else add(x,y),add(y,x); } for (int i=1;i<=cnt;++i) w[i]=1; spfa(0); for (int i=1;i<=n;++i) if (dis[i]<=ss) dgs[i]=1; for (int i=1;i<=cnt;++i) { if (dgs[s[i][0]]) w[i]=Q; else if (ocp[s[i][0]]) w[i]=inf; else w[i]=P; if (s[i][0]==1||s[i][0]==n) w[i]=0; } spfa(1); cout<<dis[n]<<endl; return 0; } inline void add(int x,int y) { s[++cnt][0]=y;s[cnt][1]=o[x];o[x]=cnt; }```
by 209u03 @ 2022-08-26 10:25:03


没加头文件
by 209u03 @ 2022-08-26 10:26:03


|