本题一题多解。

理解数据

半矩阵是什么意思？样例：

3
5 15
7

其实矩阵的对应关系是：

X | 2 3 4 5 ... 到
--+----------
1 | 5 15
2 | 7
3 |
4 |
...
从

即，1=>2 距离 $5$ ，1=>3 距离 $15$ ，2=>3 距离 $7$ 。

CODE

最短路

建个图即可。

Floyed

#include<bits/stdc++.h>
using namespace std;
int g[205][205],n; 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			g[i][j]=0x3f3f3f;
	for(int i=1;i<=n-1;i++)
		for(int j=i+1;j<=n;j++)
			cin>>g[i][j];
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(g[i][j]>g[i][k]+g[k][j])
					g[i][j]=g[i][k]+g[k][j];
	cout<<g[1][n];
	return 0;
}

玄学死了的SPFA

#include<bits/stdc++.h>
using namespace std;
class edge
{
	public:
		int next,len,end;
}e[500000];
int head[205]={0},cnt=0,n,dis[205]={0},vis[205]={0};
queue<int>q;
void add(int x,int y,int len)
{
	e[++cnt]=(edge){head[x],len,y};
	head[x]=cnt;
}
void spfa(int x)
{
	for(int i=1;i<=n;i++)
		dis[i]=0x3f3f3f;
	q.push(x);
	dis[x]=0,vis[x]=1;
	while(!q.empty())
	{
		int tnext=q.front();
		q.pop();
		vis[tnext]=0;
		for(int i=head[tnext];i;i=e[i].next) 
		{
			int tend=e[i].end;
          	if(dis[tend]>dis[tnext]+e[i].len)
            {
                dis[tend]=dis[tnext]+e[i].len;
                if(!vis[tend])
                	q.push(tend),vis[tend]=1;
            }
		}
	}
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
		for(int j=i+1;j<=n;j++)
        {
			int a;
			cin>>a;
			add(i,j,a);
		}
	spfa(1);
	cout<<dis[n];
	return 0;
}

dijkstra

#include<bits/stdc++.h>
using namespace std;
class edge
{
	public:
		int next,len,end;
}e[5000000];
class node
{
	public:
		int name,dis;
};
bool operator < (node a,node b)
{
	return a.dis>b.dis;
}
int head[205]={0},cnt=1,n,m,dis[205]={0},vis[205]={0};
priority_queue<node>q;
void add(int x,int y,int len)
{
	e[++cnt]=(edge){head[x],len,y};
	head[x]=cnt;
}
void dijkstra(int x)
{
	for(int i=1;i<=n;i++)
		dis[i]=0x3f3f3f,vis[i]=0;
	while(!q.empty())
		q.pop();
	dis[x]=0,q.push((node){x,dis[x]});
	while(!q.empty())
	{
		int tnext=q.top().name;
		q.pop();
		if(vis[tnext])
			continue; 
		vis[tnext]=1;
		for(int i=head[tnext];i;i=e[i].next) 
		{
			int tend=e[i].end;
          	if(dis[tend]>dis[tnext]+e[i].len)
          	{
          		dis[tend]=dis[tnext]+e[i].len;
				q.push((node){tend,dis[tend]});
			}
		}
	}
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
		for(int j=i+1;j<=n;j++)
		{
			int a;
			cin>>a;
			add(i,j,a);
		}
	dijkstra(1);
	cout<<dis[n];
	return 0;
}

动态规划

dfs 记忆化 dp

#include<bits/stdc++.h>
using namespace std;
int n,g[205][205],dp[205][205];
int dfs(int x,int y)
{
	if(dp[x][y]!=dp[0][0])
		return dp[x][y];
	dp[x][y]=g[x][y]; 
	for(int i=x+1;i<=y;i++)
		dp[x][y]=min(dp[x][y],dfs(x,i)+dfs(i,y));
	return dp[x][y];
}
int main()
{
	scanf("%d",&n);
	memset(g,0x3f3f3f,sizeof(g));
	memset(dp,0x3f3f3f,sizeof(g));
	for(int i=1;i<=n-1;i++)
		for(int j=i+1;j<=n;j++)
			scanf("%d",&g[i][j]);
	cout<<dfs(1,n);
	return 0;
}

递推 dp

#include<bits/stdc++.h>
using namespace std;
int a[220],g[220][220],n;
int main()
{
    memset(a,0x3f3f3f,sizeof(a));
    cin>>n;
    for(int i=1;i<n;i++)
    	for(int j=i+1;j<=n;j++)
    		cin>>g[i][j];
    a[1]=0;
    for(int i=2;i<=n;i++)
    	for(int j=1;j<=i-1;j++)
    		a[i]=min(a[i],a[j]+g[j][i]);
    cout<<a[n];
    return 0;
}//orz最短

拓扑排序

#include <bits/stdc++.h>
using namespace std;
const int N=205;
const int M=N*N;
struct node
{ 
	int to,len,nex;
}e[M];
int n,cnt,head[N],dis[N],vis[N],in[N];
inline void add(int x,int y,int z)
{
	e[++cnt]=(node){y,z,head[x]};
    head[x]=cnt;   
}
queue<int>q;
void topsort()
{
	memset(dis,0x3f3f3f,sizeof(dis)),dis[1]=0;
	for(int i=1;i<=n;i++)
    	if(!in[i])
      		q.push(i); 
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nex)
		{
			int v=e[i].to,len=e[i].len;
			dis[v]=min(dis[v],dis[u]+len);
			in[v]--;
			if(!in[v]) q.push(v);	 
		}
	} 
	return;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n-1;i++)
		for(int j=i+1;j<=n;j++)
    	{
			int len;
			cin>>len;
			add(i,j,len),in[j]++;
   		}
	topsort();
	cout<<dis[n];
	return 0;
}