题目描述

Island 发生了一场***！现在 Rinne 要和 Setsuna 立马到地上世界去。
众所周知：Island 是有一些奇怪的城镇和道路构成的（题目需要，游戏党勿喷），有些城镇之间用双向道路连接起来了，且每条道路有它自己的距离。但是有一些城镇已经被派兵***，虽然主角可以逆天改命强闯，但是为了体验该游戏的平衡性，他们只能穿过不超过 K 次被***的城镇。
定义“穿过”：从一个***的点出发到达任意一个点，都会使得次数加1
现在他们想从 1 号城镇最快的走到 n 号城镇（即出口），现在他们想让你告诉他们最短需要走多少路。

输入描述:

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

输出描述:

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

题解

第一种做法是最短路dp，对于普通的最短路来说，此题加入了一个限制条件，对于某些点最多可以经过k次，那么我们设置dis[i][k]为1到i经过k次有限制的点，对于其转移方程，我们结合最短路算法来看，依然是不断的进行松弛，一旦次数超过k次便不再更新。
具体细节看一下代码注释吧，我这什么语文功底越说越乱....

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=1e3+100;
int n,m,k;
int a[N];
struct node{
    int to,net,w;
}s[N*8];//链式前向星存图
struct star{
    int u,tim;//u表示节点，tim表示经过次数
    ll w;//w表示1到u的距离
    bool operator < (const star & rhs)const{
        return w>rhs.w;
    }
};
int tot=0,head[N];
ll dis[N][20];
void add(int u,int v,int w){
    s[++tot]={v,head[u],w};
    head[u]=tot;
}//加边
void dij(){
    priority_queue<star> Q;
    Q.push({1,0,0});
    dis[1][0]=0;
    while(!Q.empty()){
        star now=Q.top();
        Q.pop();
        for(int i=head[now.u];~i;i=s[i].net){
            int nowtim=now.tim+a[now.u];//计算是第几次经过限制点
            if(nowtim>k)continue;//如果大于k次便不再更新
            if(dis[s[i].to][nowtim]>dis[now.u][now.tim]+s[i].w){
                dis[s[i].to][nowtim]=dis[now.u][now.tim]+s[i].w;//对其进行更新
                Q.push({s[i].to,nowtim,dis[s[i].to][nowtim]});
            }
        }
    }
    ll ans=1e18;
    for(int i=0;i<=k;++i)ans=min(ans,dis[n][i]);//遍历可以走到n的所有状态，找一个最小的
    if(ans==1e18)puts("-1");
    else print(ans),putchar(10);
}
////////////////////////////////////////////////////////////////////////
int main(){
    fill(head,head+N,-1);
    memset(dis,0x3f,sizeof(dis));
    n=gn(),m=gn(),k=gn();
    repi(i,1,n){
        a[i]=gn();
    }
    repi(i,1,m){
        int u=gn(),v=gn();
        ll w=gl();
        add(u,v,w);
        add(v,u,w);
    }
    dij();
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/