链接：https://ac.nowcoder.com/acm/contest/26077/1031
来源：牛客网

题目描述

输入描述:

第一行三个整数 n,m,k，分别表示城镇数量，边数量和最多能闯过被戒严的城市的次数。
接下来 n 行，每行一个整数 1 或 0，如果为 1 则表示该城市已被戒严，0 则表示相反。
接下来 m 行，每行三个数 u,v,w，表示在 u 城镇和 v 城镇之间有一条长度为 w 的双向道路。

输出描述:

输出一行一个数字，表示从 1 到 n 的最短路径，如果到达不了的话，请输出 -1。

输入

4 5 1
1
0
1
0
1 2 10
2 3 10
3 1 15
1 4 60
3 4 30

输出

60

备注:

2≤n≤800,1≤m≤4000,1≤k≤10,1≤w≤1062 \leq n \leq 800,1 \leq m \leq 4000,1 \leq k \leq 10,1 \leq w \leq 10^62≤n≤800,1≤m≤4000,1≤k≤10,1≤w≤106

分析

1.分层图

为每对节点在每一层 建立一条边

1.如果当前节点没有阻塞，就可以直接走到同层另一个节点

2.如果当前节点有阻塞，就需要从当前节点走到下一层的另一个节点

跑最短路

在 给定层数里，取 其中 可以到达终点的层 到达终点的最短路

//-------------------------代码----------------------------

#define int ll
const int N = 2e6+10;
int n,m,k;
int e[N],ne[N],w[N],h[N],idx;
int a[N];
int dis[N];
void add(int a,int b,int c) {e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++ ;}
bool vis[N];

void dij() {
    ms(dis,inf);dis[1] = 0;
    priority_queue<pii,V<pii>,greater<pii>> q;
    q.push({0,1});
    while(q.size()) {
        auto tmp = q.top();q.pop();
        if(vis[tmp.second]) continue;
        vis[tmp.second] = 1;
        for(int i = h[tmp.second];~i;i=ne[i]) {
            int j = e[i];
            if(dis[j] > w[i] + tmp.x) {
                dis[j] = w[i] + tmp.x;
                q.push({dis[j],j});
            }
        }
    }
}

void solve() {
    cin>>n>>m>>k;
    ms(h,-1);
    fo(i,1,n) cin>>a[i];
    fo(i,1,m) {
        int x,y,z;cin>>x>>y>>z;
        if(!a[x]) {
            fo(j,0,k) add(x + n * j,y + n * j,z);//当前层
        }
        if(!a[y]) {
            fo(j,0,k) add(y + n * j,x + n * j,z);
        }
        if(a[x]) {
            fo(j,0,k-1) add(x + n * j,y + n * (j+1),z);
        }
        if(a[y]) {
            fo(j,0,k-1) add(y + n * j,x + n * (j+1),z);
        }
    }
    if(k < 0) {None;rt;}
    dij();
    int ans = inf;
    fo(i,1,k+1) ans = min(ans,dis[i*n]);
    if(ans == inf) ans = -1;
    cout<<ans<<endl;
}

void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

2.最短路+DP

分析

线性DP是到了某个点 j ，就从前面的点 i 更新过来

这题随着点数的增加，k 会逐渐变大，路程会逐渐变大，当前枚举到的点会变化

所以设状态为 dp [i][ k] 表示当前枚举到 j 点，已经经历了 k 个障碍

由于要跑 到点 n 的最小路径，所以跑dijkstra

当枚举到新的点，更新当前的 k 就可以一路跑到 n 点了。

//-------------------------代码----------------------------

//#define int ll
const int N = 1e5+10;
int n,m,k;
int e[N],h[N],w[N],ne[N],idx;
int dis[N][15];
void add(int a,int b,int c) {
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++ ;
}
struct node {
    int id,c,k;
    bool operator<(const node & x) const {
        return c > x.c;
    }
};

int a[N];
bool vis[N];

void dij() {
    ms(dis,inf);
    dis[1][0] = 0;
    priority_queue<node> q;
    q.push({1,0,0});
    while(q.size()) {
        auto tmp = q.top();q.pop();;
        if(vis[tmp.id]) continue;
        vis[tmp.id] = 1;
        for(int i = h[tmp.id];~i;i=ne[i]) {
            int j = e[i];int nowk = a[tmp.id] + tmp.k;
            if(nowk > k) continue;
            if(dis[j][nowk] > w[i] + tmp.c) {
                dis[j][nowk] = w[i] + tmp.c;
                q.push({j,dis[j][nowk],nowk});
            }
        }
    }
}

void solve()
{

    cin>>n>>m>>k;
    for(int i = 1; i<=n; i++) cin>>a[i];
    ms(h,-1);
    for(int x,y,w,i = 1; i<=m; i++) {
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    }
    dij();
    int ans = INF;
    for(int i=0; i<=k; i++) {
        ans=min(ans,dis[n][i]);
    }
    if(ans==INF) puts("-1");
    else printf("%d\n",ans);
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------