孩子们这题第一眼就是floyd，然后就错了注意一下只能从编号小的往编号大的走，所以考虑用DP（不可能）

这就是裸的dijkstra板子，建个图就行，权值不为零且i<j的连边，然后直接跑一边dijkstra，代码就在我的讨论里（）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=5e5+10;
struct edge{
	int to,dis,nxt;
}e[maxm];
int dis[maxn],cnt,head[maxn];
bool vis[maxn];
int n,m,s,u,v,d;
int mp[105][105];
struct node{
	int dis;
	int pos;
	bool operator<(const node &x)const{
		return x.dis<dis;
	}
};
priority_queue<node> q;

void add1(int u,int v,int d){
	e[++cnt].dis=d;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

void dijkstra(){
	dis[s]=0;
	q.push((node){0,s});
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int x=tmp.pos,d=tmp.dis;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis){
				dis[y]=dis[x]+e[i].dis;
				if(!vis[y]) q.push((node){dis[y],y});
			}
		}
	}
}

int main(){
	scanf("%d",&n);
	s=1;
	memset(dis,0x7f,sizeof(dis));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&mp[i][j]);
			if(mp[i][j]&&i<j) add1(i,j,mp[i][j]);
		}
	}
	dijkstra();
	printf("%d ",dis[n]);
	return 0;
} 

远古题解

#include<bits/stdc++.h>
using namespace std;
int map1[101][101];
int dc[10001];
int main()
{
int n,x;
cin>>n;
for(int i=1;i<=n;i++)
{
dc[i]=100001;//由于要取每一层的最小值，初始化的大一些
for(int j=1;j<=n;j++)
{
cin>>map1[i][j];
}
}
dc[1]=0;//边界（第一个城市到第一个城市当然为零啦~）
for(int i=2;i<=n;i++)//思路，列举到达每一个城市的可能，然后取最小值叠加转移状态
{
for(int j=1;j<=i;j++)
{
if(map1[i][j])//如果有路的话
{
dc[i]=min(dc[i],dc[j]+map1[i][j]);//这个的过程实际上就是在比较当前到达这个城市的距离与另外的路
}
}
}
cout<<dc[n];//推到最后的终点就出来了~
return 0;//华丽的结束
}
//动态规划对初学者还是很难的，但它同时又是进阶的必备，所以一定要好好学啦~
//最后再送上一句动态规划的条件，也是特别有哲理的一句话：
//现在决定未来，外来与过去无关

楼下更6

询问chatGPT得到的Accepted答案

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f; // 表示无穷大的值，即两个城市之间没有路

int main()
{
    int n;
    cin >> n;
    
    vector<vector<int>> map(n, vector<int>(n)); // 表示城市之间距离的矩阵
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
    
    vector<int> dist(n, INF); // dist[i]表示从1号城市到i号城市的最短距离
    dist[0] = 0;
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; // 小根堆，用来辅助Dijkstra算法
    
    pq.push({0, 0}); // 将1号城市放入小根堆
    
    while (!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d != dist[u]) continue; // 如果pq中取出的最短距离不是当前最短距离，则需要跳过
        
        for (int v = u + 1; v < n; v++) // 对于所有比u大的城市v，更新dist[v]
        {
            if (map[u][v] != 0 && dist[u] + map[u][v] < dist[v]) // 如果有路相连，并且通过u可以更新dist[v]
            {
                dist[v] = dist[u] + map[u][v]; // 更新dist[v]
                pq.push({dist[v], v}); // 将v放入小根堆，用于后续处理
            }
        }
    }
    
    cout << dist[n-1] << endl; // 输出最短距离
    
    return 0;
}