题目大意
有$N$个城市，其中有部分城市被僵尸占领，不能通过。
如果一个城市距离被占领城市的距离不超过$S$，这就是一个危险城市，经过这种城市的代价比普通的城市要高
现在要从$1$走到$N$，求代价
坑点
- 被占领的城市不能通过，因为僵尸会吃了你的脑子。。。
- 在$1$号节点和$N$号节点不需要住店所以通往这两个节点的花费是$0$
- 记得要开$longlong$
- 极大值不能只开到$2147483647$，因为这是$longlong$
思路
将被占领的城市进行标记，
在输入边的时候，如果是与被占领城市相连，那么就变成与0号节点相连，0和0不连边
处理完之后，以0为起点跑最短路，
处理所有dis小于s的城市，这些城市就是危险城市
到这些危险城市的代价就可以修改了
然后以1为起点跑最短路，到最后就可以得到答案了
附赠样例
附赠一组样例
21 26 2 21000 20005 16 1 2 1 3 1 10 2 5 3 4 4 6 5 8 6 7 7 9 8 10 9 10 9 11 11 13 12 13 12 15 13 14 13 16 14 17 15 16 15 18 16 17 16 19 17 20 18 19 19 20 19 21Out 15000
代码
#include#include #include #include #include #define LL long long#define INF 21474836470000using namespace std;const int maxnode = 1e5+3;const int maxedge = 4e5+6;inline int readInt() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while (c <= '9' && c >= '0') { x = x*10 + c-'0'; c = getchar(); } return x * f;}inline LL readLL() { LL x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while (c <= '9' && c >= '0') { x = x*10 + x-'0'; c = getchar(); } return x * f;}int n, m, k, s, K, first[maxnode], next[maxedge];bool book[maxnode], vis[maxnode];int u[maxedge], v[maxedge], q, p;long long w[maxedge], dis[maxnode];inline void addedge(int f, int i) { next[i] = first[f]; first[f] = i;}inline void SPFA(int sta) { deque Q; memset(vis, 0, sizeof(vis)); for(int i=1; i<=n; i++) dis[i] = INF; dis[sta] = 0; vis[sta] = 1; Q.push_back(sta); int x, k; while(!Q.empty()) { x = Q.front(); k = first[x]; Q.pop_front(); while (k != -1) { if(dis[v[k]] > dis[u[k]] + w[k]) { dis[v[k]] = dis[u[k]] + w[k]; if(!vis[v[k]]) { vis[v[k]] = 1; if(!Q.empty()) { if(dis[v[k]] < dis[Q.front()]) Q.push_front(v[k]); else Q.push_back(v[k]); } else Q.push_front(v[k]); } } k = next[k]; } vis[x] = 0; }}int main() { n = readInt(), m = readInt(), k = readInt(), s = readInt(); p = readInt(), q = readInt(); for(int i=1; i<=k; i++) { K = readInt(); book[K] = 1; } memset(first, -1, sizeof(first)); for(int i=1; i<=2*m; i++) { u[i] = readInt(), v[i] = readInt(), w[i] = 1LL; u[i] = (book[u[i]]) ? 0 : u[i]; v[i] = (book[v[i]]) ? 0 : v[i]; if(u[i] == v[i] && v[i] == 0) {i++; continue;} u[i+1] = v[i], v[i+1] = u[i], w[i+1] = w[i]; addedge(u[i], i); i++; addedge(u[i], i); } SPFA(0); for(int i=1; i<=2*m; i++) { if(book[u[i]] || book[v[i]] || u[i] == 0 || v[i] == 0) w[i] == INF; else if(v[i] == n || v[i] == 0) w[i] = 0; else if(dis[v[i]] <= s) w[i] = q; else w[i] = p; } SPFA(1); printf("%lld", dis[n]);}