http://www.lydsy.com/JudgeOnline/problem.php?id=1922 (题目链接)
题意
一张无向图，每个节点被k个节点保护，想要走到一个节点当且仅当它不被保护。你可以从1号节点放出无限个炸弹去炸毁节点，问最少需要多久才可以炸毁n号节点。
Solution
昨天考试题。
一看就是最短路然后带一些特殊处理，怎么特殊处理呢？我们使用Dijkstra来做这道题，因为SPFA可以重复入队，所以是错误的。每次出堆的点，将它保护的节点的“保护度数”减1并更新被保护节点的dis（取max），如果某个节点的度数已经被减成了0，并且它的dis不是inf，也就是说已经有一个炸弹在这个节点蓄势待发了，我们将这个节点加入堆中。做完减少度数操作后，就是正常的Dijkstra的入堆操作了，记得只有“保护度数”为0的点才能入堆。
细节
邻接表的数组开成了节点个数的大小→_→
代码
// bzoj1922
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#define LL long long
#define inf 1e18
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=5010,maxm=100010;
struct edge {int to,next,w;}e[maxm<<1];
struct data {
int num;LL w;
friend bool operator < (const data a,const data b) {
return a.w>b.w;
}
};
LL dis[maxn];
int head[maxn],vis[maxn],r[maxn];
int cnt,n,m;
vector<int> v[maxn]; void link(int u,int v,int w) {
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=w;
}
void Dijkstra() {
for (int i=1;i<=n;i++) dis[i]=inf;
dis[1]=0;
priority_queue<data> q;
q.push((data){1,0});
while (!q.empty() && !vis[n]) {
data x=q.top();q.pop();
if (vis[x.num]) continue;
vis[x.num]=1;
for (int i=0;i<v[x.num].size();i++) {
r[v[x.num][i]]--;
if (!r[v[x.num][i]] && dis[v[x.num][i]]!=inf)
q.push((data){v[x.num][i],max(dis[v[x.num][i]],x.w)});
dis[v[x.num][i]]=max(dis[v[x.num][i]],x.w);
}
for (int i=head[x.num];i;i=e[i].next) {
if (!vis[e[i].to] && dis[e[i].to]>x.w+e[i].w) {
dis[e[i].to]=x.w+e[i].w;
if (!r[e[i].to]) q.push((data){e[i].to,dis[e[i].to]});
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
for (int uu,vv,ww,i=1;i<=m;i++) {
scanf("%d%d%d",&uu,&vv,&ww);
link(uu,vv,ww);
}
for (int i=1;i<=n;i++) {
scanf("%d",&r[i]);
for (int x,j=1;j<=r[i];j++) {
scanf("%d",&x);
v[x].push_back(i);
}
}
Dijkstra();
printf("%lld",dis[n]);
return 0;
}