問題描述

幻想歷8012年5月12日深夜，斯普林·布拉澤降下神諭：“Trust me, earn eternal life.”克里斯軍團士氣大增。作為克里斯軍團的主帥，你決定利用這一機會發動奇襲，一舉擊敗傑森國。具體地説，傑森國有N個城市，由M條單向道路連接。神諭鎮是城市1而傑森國的首都是城市N。你只需摧毀位於傑森國首都的曾·布拉澤大神殿，傑森國的信仰，軍隊還有一切就都會土崩瓦解，灰飛煙滅。

為了儘量減小己方的消耗，你決定使用自爆機器人完成這一任務。唯一的困難是，傑森國的一部分城市有結界保護，不破壞掉結界就無法進入城市。而每個城市的結界都是由分佈在其他城市中的一些結界發生器維持的，如果想進入某個城市，你就必須破壞掉維持這個城市結界的所有結界發生器。

現在你有無限多的自爆機器人，一旦進入了某個城市，自爆機器人可以瞬間引爆，破壞一個目標（結界發生器，或是傑森國大神殿），當然機器人本身也會一起被破壞。你需要知道：摧毀傑森國所需的最短時間。

輸入格式

輸入文件的landcraft.in的第一行兩個正整數N, M。

接下來M行，每行三個正整數ui, vi, wi，表示有一條從城市ui到城市vi的單向道路，自爆機器人通過這條道路需要wi的時間。

之後N行，每行描述一個城市。首先是一個正整數li，維持這個城市結界所使用的結界發生器數目。之後li個1~N之間的城市編號，表示每個結界發生器的位置。如果li = 0，則説明該城市沒有結界保護，保證l1 = 0 。

輸出格式：

輸出文件landcraft.out僅包含一個正整數 ，擊敗傑森國所需的最短時間。

 

分層圖，做了這麼久的圖論第一次寫了一個高級點的最短路啊。

題解參考黃學長

帶限制的最短路。。。

設d1[x],d2[x]為城市x的到達時間，可進入時間

max(d1[x],d2[x])為真實的進入時間

d[x]記錄城市x被多少個城市保護

每次堆中取出一個真實進入時間最小的城市

更新它所通往的城市的d1，保護城市的d2

保護城市的d–

若d=0，則可入堆

複雜度(n+m)logn

//bzoj1922 大陸爭霸 分層圖dijkstra 
#include<bits/stdc++.h>
using namespace std;
#define maxn 3005
#define pa pair<int,int>
#define ll long long 
int n,m,cnt;
int head[maxn];
int d1[maxn],d2[maxn],d[maxn];
int l[maxn],a[maxn][maxn];
bool vis[maxn];
struct edge{
    int next,to,w;
}e[70005];
priority_queue<pa,vector<pa>,greater<pa> >q;
void insert(int u,int v,int w){
    cnt++;
    e[cnt].next=head[u];e[cnt].to=v;e[cnt].w=w;
    head[u]=cnt;
}
void dijkstra(){
    memset(d1,127,sizeof d1);//使用優先隊列存兩個值 
    q.push(make_pair(0,1));//第一個是到達時間，第二個是到達的點 
    d1[1]=0;
    while(!q.empty()){
        int now=q.top().second;
        q.pop();
        if(vis[now])continue;vis[now]=1;
        int mx=max(d1[now],d2[now]);
        for(int i=head[now];i;i=e[i].next)
        {
            int s=e[i].to;
            if(mx+e[i].w<d1[s])
            {
                d1[s]=mx+e[i].w;
                int tmp=max(d1[s],d2[s]);
                if(!d[s])q.push(make_pair(tmp,s));    
            }
        }
        for(int i=1;i<=l[now];i++)
        {
            int t=a[now][i];
            d[t]--;d2[t]=max(d2[t],mx);
            int tmp=max(d1[t],d2[t]);
            if(!d[t])q.push(make_pair(tmp,t));    
        }
    }
    printf("%d\n",max(d1[n],d2[n]));
}
int main(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        if(u!=v)insert(u,v,w);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&d[i]);
        for(int j=1;j<=d[i];j++){
            scanf("%d",&u);
            a[u][++l[u]]=i;//l[x]是在x城市有的結界數論
            //a[x][y]是在x城市的第y個結界守護的城市 
        }
    }
    dijkstra();
    return 0;
}