小明的跳格子

#include<cstring>//memcpy
#include<limits.h>//INT_MAX
#include<algorithm>//fill
#define MAX 505
using namespace std;
typedef struct MatGraph
{
	long long int edge[MAX][MAX];
	int n,e;
}MatGraph;
long long int dist[MAX];//最短路径
void Dijkstra(MatGraph g,int v)
{
	int S[MAX]={0};//保存已加入S的集合
	for(int i=0;i<g.n;i++)
	{
		dist[i]=g.edge[v][i];//距离初始化
		S[i]=0;//一开始S里面空的
	}
	S[v]=1;//将v源点加入S集合
	for(int i=0;i<g.n-1;i++)
	{//去掉源点，到其他点的所有最短
		int Min=INT_MAX/2,u;//u用来记录
		for(int j=0;j<g.n;j++)
		{//依托最近点，次最近点.....这样的已知信息序列合集来不断进行更新最短路径
			//所以能够确保每轮递推找到的那个最短点是最终结果
			if(S[j]==0&&dist[j]<Min)
			{
				u=j;
				Min=dist[j];
			}
		}
		S[u]=1;//纳入s集合了
		for(int j=0;j<g.n;j++)
		{
			if(S[j]==0)
			{//根据新加入的最短点作为中转点更新最短路径,INT_MAX一半是防止相加溢出
				if(g.edge[u][j]!=INT_MAX/2&&dist[u]+g.edge[u][j]<dist[j])
				{//保证有从新最短点到j的边，且经过它中转比原来的更短
					dist[j]=dist[u]+g.edge[u][j];
				}
			}
		}	
	}	
}
long long int MAT[MAX][MAX];//中转的邻接矩阵数组
int main(void)
{
	//a[i]=2则i可以直达j=2，那如果要到j=1，就要用一次魔法，到j=3没办法
	//所以可以推测i->j的魔法代价为a[i]-j,为负数就是没法达，0就是直达
	//我们基本不可能直接抵达终点，就要经过一系列中转点
	//而且要求最少代价，就可以联想到Dijkstra求解最短路径，权重就为a[i]-j
	int n;
	scanf("%d",&n);
	long long int a[n+5];
	for(int i=0;i<n-1;i++)//小心a的个数是n-1
		scanf("%lld",&a[i]);
	MatGraph G;
	G.n=n;
	fill(MAT[0],MAT[0]+MAX*MAX,INT_MAX/2);//先初始化权重为无穷（/2防相加溢出）
	for(int i=0;i<n-1;i++)
	{//a只到n-1哦
		for(int j=0;j<n;j++)
		{//目的地当然不止到n-1
			if(a[i]-j-1>=0)//负数当然不给它权重啦
				MAT[i][j]=a[i]-j-1;//邻接矩阵赋值权重
		//实际中记得补上1的差值对应回数组下标啦
		}
	}
	memcpy(G.edge,MAT,sizeof(MAT));//复制到MatGraph里的邻接矩阵
	Dijkstra(G,0);
	if(dist[n-1]!=INT_MAX/2)
		printf("%lld",dist[n-1]);
	else
		printf("-1");
	
	return 0;
}