Luogu | P2446 [SDOI 2010] 大陆争霸 | 图论 | 最短路

Description

幻想历 8012年5月12日 深夜，斯普林·布拉泽 降下神谕：“Trust me, earn eternal life.”克里斯军团士气大增。作为克里斯军团的主帅，你决定利用这一机会发动奇袭，一举击败杰森国。具体地说，杰森国有 $N$ 个城市，由 $M$ 条单向道路连接。神谕镇是城市 $1$ 而杰森国的首都是城市 $N$ 。你只需摧毁位于杰森国首都的曾·布拉泽大神殿，杰森国的信仰，军队还有一切就都会土崩瓦解，灰飞烟灭。

为了尽量减小己方的消耗，你决定使用自爆机器人完成这一任务。唯一的困难是，杰森国的一部分城市有结界保护，不破坏掉结界就无法进入城市。而每个城市的结界都是由分布在其他城市中的一些结界发生器维持的，如果想进入某个城市，你就必须破坏掉维持这个城市结界的所有结界发生器。

现在你有无限多的自爆机器人，一旦进入了某个城市，自爆机器人可以瞬间引爆，破坏一个目标（结界发生器，或是杰森国大神殿），当然机器人本身也会一起被破坏。你需要知道：摧毁杰森国所需的最短时间。

Input Format

第一行为两个正整数 $N, M$ 。

接下来 $M$ 行，每行三个正整数 $u_i, v_i, w_i$，表示有一条从城市 $u_i$ 到城市 $v_i$ 的单向道路，自爆机器人通过这条道路需要 $w_i$ 的时间。

之后 $N$ 行，每行描述一个城市。首先是一个正整数 $l_i$，维持这个城市结界所使用的结界发生器数目。之后 $l_i$ 个 $1 \sim N$ 之间的城市编号，表示每个结界发生器的位置。如果 $l_i = 0$，则说明该城市没有结界保护，保证 $l_1 = 0$ 。

Output Format

一个正整数 ，击败杰森国所需的最短时间。

Input Sample

Sample 01

6 6
1 2 1
1 4 3
2 3 1
2 5 2
4 6 2
5 3 2
0
0
0
1 3
0
2 3 5

Output Sample

Sample 01

5

Data Range

$N \le 3 \times 10^3$，$M \le 7 \times 10^4$，$w_i \le 10^8$。

输入数据一定有解。

Solution

最短路。每次节点入队时查询一下结界是否打开，如果没打开就将那个结点放在一边等等再入队。

Code

#include<queue>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::vector;
using std::priority_queue;

typedef long long ll;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct pt{
    int id;
    ll dis;
    friend bool operator < (pt a,pt b){
        return a.dis>b.dis;
    }
};

struct edge{
    int from;
    int to;
    int next;
    int w;
}e[70005];

int N;
int M;
int node;

int first[3005];
int last[3005];
int cnt[3005];

ll dist[3005];
ll wait[3005];

bool done[3005];

vector<int>v[3005];
priority_queue<pt>pq;

void addedge(int u,int v,int w){
    e[++node]=(edge){u,v,0,w};
    if(first[u]==0) first[u]=node;
    else e[last[u]].next=node;
    last[u]=node; return;
}

void Dijkstra(){
    wipe(wait,0x3f);
    wipe(dist,0x3f);
    dist[1]=0;
    pq.push((pt){1,0});
    while(!pq.empty()){
        pt x=pq.top(); pq.pop();
        if(done[x.id])
            continue;
        done[x.id]=1;
        rep(i,0,v[x.id].size()-1){
            cnt[v[x.id][i]]--;
            if(cnt[v[x.id][i]]==0){
                if(wait[v[x.id][i]]<0x3f3f3f3f3f3f3f3f){
                    dist[v[x.id][i]]=max(dist[x.id],wait[v[x.id][i]]);
                    pq.push((pt){v[x.id][i],dist[v[x.id][i]]});
                }
            }
        }
        for(int p=first[x.id];p;p=e[p].next){
            int y=e[p].to;
            if(cnt[y]==0){
                if(dist[y]>dist[x.id]+e[p].w){
                    dist[y]=dist[x.id]+e[p].w;
                    pq.push((pt){y,dist[y]});
                }
            }
            else
                wait[y]=min(wait[y],dist[x.id]+e[p].w);
        }
    }
    return;
}

int main(){
    int f,t,w;
    Read(N);
    Read(M);
    rep(i,1,M){
        Read(f);
        Read(t);
        Read(w);
        addedge(f,t,w);
    }
    rep(i,1,N){
        Read(cnt[i]);
        rep(j,1,cnt[i]){
            Read(w);
            v[w].push_back(i);
        }
    }
    Dijkstra();
    printf("%lld\n",dist[N]);
    return 0;
}