题目链接：https://cn.vjudge.net/contest/276233#problem/C
AC代码：
#include<iostream>
#include<cstring>
#include<stack>
#include<iomanip>
#include<cmath>
#include<queue>
#include<algorithm>
#include<stdio.h>
using namespace std;
# define ll long long
# define inf 1ll<<
const int maxn = +;
const int maxedge= +;
int n;
ll m;
int num,head[maxn];
ll dis[maxn];
int out[maxn],vis[maxn];
struct node
{
int fr;
int to;
ll cost;
int nex;
} edge[maxedge];
struct point
{
int num;
int id;
} po[maxn];
bool cmp(point t1,point t2)
{
return t1.num<t2.num;
}
void init()
{
for(int i=; i<=n; i++)
{
head[i]=-;
out[i]=;
vis[i]=;
dis[i]=inf;
}
num=;
}
void addedge(int fr,int to,ll cost)
{
edge[num].to=to;
edge[num].cost=cost;
edge[num].nex=head[fr];
head[fr]=num++;
}
ll spfa(int st,int ed)
{
dis[st]=;
vis[st]=;
queue<int>q;
q.push(st);
while(!q.empty())
{
int tmp=q.front();
q.pop();
vis[tmp]=;
out[tmp]++;
if(out[tmp]>n)
return -;
for(int i=head[tmp]; i!=-; i=edge[i].nex)
{
int u=edge[i].to;
if(dis[u]>dis[tmp]+edge[i].cost)
{
dis[u]=dis[tmp]+edge[i].cost;
if(vis[u])
continue;
vis[u]=;
q.push(u);
}
}
}
return dis[ed];
}
int main()
{
int T;
scanf("%d",&T);
int Case=;
while(T--)
{
scanf("%d %lld",&n,&m);
init();
for(int i=; i<=n; i++)
{
scanf("%d",&po[i].num);
po[i].id=i;
}
for(int i=; i<n; i++)
{
addedge(i+,i,-);
}
sort(po+,po+n+,cmp);
for(int i=; i<n; i++)
{
int u=po[i+].id;
int v=po[i].id;
if(u>v)
swap(u,v);
addedge(u,v,m);
}
int t1=po[].id;
int t2=po[n].id;
if(t1>t2)
swap(t1,t2);
ll ans=spfa(t1,t2);
printf("Case %d: %lld\n",++Case,ans);
}
return ;
}