[SDOI2010]大陆争霸

带限制的最短路

这道题是我做的第一个带限制的最短路题，所以许多细节我思考了好长时间并看了题解才会的。

首先我们关注条件：机器人无限个，所以我们可以认为有无限个机器人从1号点同时出发。摧毁一个点的代价为max（到达他的代价，破坏他的所有的保护器的代价）；所以我们可以开三个数组和一个vector。三个数组分别表示到达该点的代价d1，破坏他的所有的保护器的代价d2，还有他有多少个保护器inde。vector用来存该点保护了哪些点，我一开始想反了。为什么要这样？我们更新摧毁该点的代价时可以更新他保护的城市的d2。最后一遍dij就好了（见代码注释）

code：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#define SUPER_INT signed
using namespace std;
const int maxn=400006;
struct hzw
{
    int to,next,v;
}e[maxn];
vector<int>v[maxn];
typedef pair<int,int>p;
int head[maxn],cur,inde[maxn],da[maxn],db[maxn],n,m,k;
inline void add(int a,int b,int c)
{
    e[cur].to=b;
    e[cur].next=head[a];
    e[cur].v=c;
    head[a]=cur++;
}
bool vis[maxn];
inline void dij(int shit)
{
    priority_queue<p,vector<p>,greater<p> >q;
    memset(da,0x3f,sizeof(da));
    da[shit]=0;
    q.push(p(0,shit));
    while (!q.empty())
    {
        p now=q.top();
        q.pop();
        int s=now.second;
        if (vis[s]) continue;
        vis[s]=1;			
		int tmp=max(da[s],db[s]);//破坏这个点实际的代价 
        for (int i=head[s];i!=-1;i=e[i].next)
        {
        	int vv=e[i].to;
        	if (da[vv]>tmp+e[i].v)
        	{
        		da[vv]=tmp+e[i].v;//更新连接的点：到达它需要的代价 
        		if (inde[vv]==0) q.push(p(da[vv],vv)); //如果本来就没有保护器，直接入队 
			}
        }
        for (int i=0;i<v[s].size();++i)
        {
        	int vv=v[s][i];
        	inde[vv]--; 
        	db[vv]=max(db[vv],tmp);//更新该点保护的城市的db值（取max，因为机器人同时出发） 
			if (!inde[vv]) q.push(p(max(db[vv],da[vv]),vv));//如果所保护的城市已经没有保护器了，就入队 
		}
    }
    cout<<max(da[n],db[n]);//good game !  
}
SUPER_INT main()
{
    memset(head,-1,sizeof(head));
	cin>>n>>m;
    for (int i=1,a,b,c;i<=m;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    for (int i=1,a;i<=n;++i)
    {
        scanf("%d",&a);
        for (int j=1,b;j<=a;++j)
        {
        	inde[i]++;
            scanf("%d",&b);
            v[b].push_back(i);
        }
    }
    dij(1);
}

收获：

带限制的最短路问题往往有几个条件，就要开几个数组，在跑最短路的过程中不断更新各个参数，注意这类形如xx受到yy，的问题：一般要存yy保护了哪些点，方便更新