分层图最短路

链接：https://ac.nowcoder.com/acm/problem/236176 来源：牛客网

做法：直接去连边的话因为数据范围过大，所以会出现tle的现象，也有段错误的现象不知道是为什么，所以对于层与层之间的边，我们建立一个平台，同层的点到这个平台的距离为0，层与层之间的距离为c，那注意不能建立一个双向的平台，这样的话会出现一些不存在的边，所以要建立一个向上的路径和向下的路径分别为i+n和i+2n，之后就是特殊边正常连，然后跑dij即可，spfa可能为卡，但如果数据弱的话也是能过的。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define int long long
/*inline __int128 readd(){
    __int128 x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline voidd print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}*/
//ddont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
//用__int128时记得删掉关流
int cnt=0;
struct ty{
    int to,next,l;
}edge[3000100];
int head[3000100];
void add(int x,int y,int z)
{
    edge[++cnt].to=y;
    edge[cnt].l=z;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
int n,m,c;
struct node
{
    int x,l;
    bool operator <(const node &t)const{
        return l>t.l;
    };
};
std::vector<int> pt[1000100];
int id[1000100];
std::map<std::pair<int,int>, int> mp;
std::priority_queue<node> q;
bool vis[1000100];
int dis[1000100];
void dij(int s)
{
    memset(dis,0x3f,sizeof(dis));
     memset(vis,false,sizeof(vis));
    q.push((node){s,0});
    dis[s]=0;
    while(!q.empty())
    {
        auto [x,l]=q.top();
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        //std::cout<<x<<endl;
        for(int i=head[x];i!=-1;i=edge[i].next)
        {
            int y=edge[i].to;
            int w=edge[i].l;
            //std::cout<<x<<" "<<y<<" "<<w<<" "<<endl;
            
            if(dis[y]>=dis[x]+w)
            {
                //std::cout<<x<<" "<<y<<" "<<w<<endl;
                dis[y]=dis[x]+w;
                q.push({y,dis[y]});
            }
        }
    }
    if(dis[n]>=1e9) dis[n]=-1;
    std::cout<<dis[n]<<endl;
}
void slove()
{
    memset(head,-1,sizeof(head));
   std::cin>>n>>m>>c;
   int dep=0;
   for(int i=1;i<=n;i++)
   {
        int x;
        std::cin>>x;
        pt[x].push_back(i);
       dep=std::max(dep,x);
   }
   for(int i=1;i<=m;i++)
   {
        int x,y,z;
        std::cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
   }
   for(int i=1;i<=dep;i++)
   {
        for(auto u:pt[i])
        {
            add(u,i+n,0);
            add(i+2*n,u,0);
        }
        if(!pt[i+1].empty())
        {
            add(i+n,i+1+2*n,c);
            add(i+1+n,i+2*n,c);
        }
   }
   dij(1);

}
signed main()
{
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}