一道洛谷不知道哪门子月赛的题
可以用此题来练习最短路算法
SPFA和dijkstra的练习题（
关于Floyed，他死了
思路：
本题是最短路板子。
首先就是建立虚点0连向被控制的点，令边长为1，SPFA一遍，求出各点到虚点的距离，然后判断没被控制的各点距离是否不大于s+1，就能处理出所有危险的点，标记一下。然后就是跑再一遍SPFA，每次判断连向的点是否被标记，然后选择边权差分约束。
但是这样算会算上到了n点的花费，而题意到了n点就不需要花费了，于是最后输出的答案还得减去多加的到n点的花费，然后就OK了（注意答案会爆int）。
code:
#include#include #include #include #include #include #define N 100005#define M 200005#define INF 1e18#define ll long longusing namespace std;struct edge { int to; int from;}e[M<<1];int cnt,head[N];inline void add_edge(int x,int y){ e[++cnt].from = y; e[cnt].to = head[x]; head[x] = cnt;}int n,m,k,s,Q,P;ll dis[N];int vis[N],c[N];void SPFA() { queue q; //for(int i=1;i<=n;i++)dis[i]=INF; memset(dis,0x3f3f3f,sizeof(dis)); for(int i = 1 ; i <= k ; i++){ dis[c[i]] = 0; vis[c[i]] = 1; q.push(c[i]); } while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i = head[u] ; i ; i = e[i].to) { int v = e[i].from; if(dis[v] > dis[u] + 1) { dis[v] = dis[u] + 1; if(!vis[v]) { vis[v] = 1; q.push(v); } } } }}ll w[N];void spfa(){ queue q; for(int i = 1 ; i <= n ; i++) { if(dis[i] <= s) w[i] = Q; else w[i] = P; dis[i] = INF; } for(int i = 1 ; i <= k ; i++) w[c[i]] = INF; vis[1] = 1; dis[1] = w[n] = w[1] = 0; q.push(1); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i = head[u] ; i ; i = e[i].to) { int v = e[i].from; if(dis[v] > dis[u] + w[u]){ dis[v] = dis[u] + w[u]; if(!vis[v]) { vis[v] = 1; q.push(v); } } } }}int main() { scanf("%d%d%d%d",&n,&m,&k,&s); scanf("%d%d",&P,&Q); for(int i = 1 ; i <= k ; i++) scanf("%d",&c[i]); for(int i = 1 ; i <= m ; i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x,y); add_edge(y,x); } SPFA(); spfa(); printf("%lld\n",dis[n]); return 0;}