分层图最短路
链接: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;
}