题目大意:有n个城市m条双向道路,还有k个已经被僵尸占领的城市,规定:被占领城市不能经过,走不超过s条道路就能到达被占领城市的算危险城市,路费Q,其他城市算安全城市,路费P。求从1走到n的最少花费(1和n路费为0)。
解题思路:我们先跑一遍BFS,求出哪些是危险城市,然后记录每个城市的路费(貌似int会爆,我用long long,把被占领城市设为0x1111111111111111LL),跑SPFA。
但是是点权怎么办?我们可以每条边的边权设为连接的两个点的点权,然后最后的答案除以2即可。
C++ Code:
#include<cstdio> #include<cctype> #include<cstring> #define C c=getchar() int n,m,k,s; long long P,Q,dis[100005],ans[100005]; int head[400005],nxt[400005],to[400005],cnt,q1[200001],q2[200001],l,r; bool vis[100005]; inline int readint(){ char C; while(!isdigit(c))C; int p=0; while(isdigit(c))p=(p<<3)+(p<<1)+(c^'0'),C; return p; } void bfs(){ memset(q2,0,sizeof(q2)); while(l!=r){ int u=q1[l=l%200000+1]; int now=q2[l]+1; if(now<=s) for(int i=head[u];i;i=nxt[i]){ int v=to[i]; if(dis[v]==-1){ dis[v]=Q; q1[r=r%200000+1]=v; q2[r]=now; } } } for(int i=1;i<=n;++i) if(dis[i]==-1)dis[i]=P; } void spfa(){ memset(q1,0,sizeof q1); memset(vis,0,sizeof(vis)); l=0,vis[1]=q1[1]=r=1; memset(ans,0x11,sizeof ans); ans[1]=0; while(l!=r){ int u=q1[l=l%200000+1]; for(int i=head[u];i;i=nxt[i]){ int v=to[i]; if(ans[v]>ans[u]+dis[u]+dis[v]){ ans[v]=ans[u]+dis[u]+dis[v]; if(!vis[v]){ vis[v]=1; q1[r=r%200000+1]=v; } } } vis[u]=0; } } int main(){ n=readint(),m=readint(),k=readint(),s=readint(); P=readint(),Q=readint(); memset(dis,-1,sizeof(dis)); dis[1]=dis[n]=0; l=r=0; while(k--){ int x=readint(); dis[x]=0x1111111111111111LL; q1[++r]=x; } cnt=0; while(m--){ int x=readint(),y=readint(); to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; } bfs(); spfa(); printf("%lld ",ans[n]/2); }