远古题解

#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;
}