题解 P3393 【逃离僵尸岛】
YF1999
2016-10-30 19:27:11
第一次发题解……紧张……表示不太会用Markdown，希望没问题
这里提供一个优先队列优化dijkstra的解题代码
思路：先BFS出危险的城市，然后再搜最短路
因为邻接表vec建立的形式，我用了一个比较笨的方法来在BFS更改路权，详情见代码
然后路权设置为目标城市的费用，去安全城市就是safe，否则是danger
注意：目标城市N的路权全部为0
代码不是特别好，还有可以优化的地方
贴一下C++代码
```cpp
#include<iostream>
#include<vector>
#include<queue>
#define Max 20000000000
using namespace std;
struct edge{
int to, distance;
};
vector<edge> vec1[100010];//用于BFS
vector<edge> vec2[100010];//将颠倒的vec1反转回来
edge e;
//dijstra优先队列优化
typedef pair<int,int> P;
priority_queue< P, vector<P>, greater<P> > que;
P p;
queue<P> que_danger;//BFS危险城市
long long int dis[100010], safe, danger;//safe表示安全城市费用，danger反之
int N, M, K, S, from, to, distance;
bool sign[100010];//标记是否被侵占
int main(){
ios::sync_with_stdio(false);//输入输出优化
cin >> N >> M >> K >> S >> safe >> danger;
//危险城市加入que_danger
for( register int i = 1; i <= N; i ++ ) sign[i] = true;
for( register int i = 0; i < K; i ++ ){
cin >> from;
sign[from] = false;//标记，dijkstra时不经过这个城市
que_danger.push( P(from,0) );
}
//建立vec1
for( register int i = 1; i <= M; i ++ ){
cin >> from >> to;
e.to = to; e.distance = safe;
vec1[from].push_back( e );
e.to = from;
vec1[to].push_back( e );
}
//危险城市BFS
while( que_danger.size() ){
p = que_danger.front();
que_danger.pop();
if( p.second == S + 1 ) break;
for( register int i = 0; i < vec1[p.first].size(); i ++ ){
if( vec1[p.first][i].distance != danger ){
vec1[p.first][i].distance = danger;//因为是出城路权改成danger，所以还要反转变为入城路权是danger
que_danger.push( P(vec1[p.first][i].to,p.second+1) );
}
}
}
//反转vec1成vec2
for( register int j, i = 1; i <= N; i ++ ){
for( j = 0; j < vec1[i].size(); j ++ ){
to = vec1[i][j].to;
e.to = i;
if( i == N ) e.distance = 0;//终点N城市入城路权为0
else e.distance = vec1[i][j].distance;
vec2[to].push_back( e );
}
}
//dijkstra
for( register int i = 2; i <= N; i ++ ) dis[i] = Max;
dis[1] = 0;
que.push( P(1,0) );
while( que.size() ){
p = que.top();
que.pop();
if( p.second > dis[p.first] ) continue;
from = p.first;
for( register int i = 0; i < vec2[from].size(); i ++ ){
e = vec2[from][i];
if( dis[from] + e.distance < dis[e.to] && sign[e.to] ){
dis[e.to] = dis[from] + e.distance;
que.push( P(e.to,dis[e.to]) );
}
}
}
cout << dis[N];
return 0;
}
```