#include<iostream> #include<algorithm> #include<cstring> #define N 25005 using namespace std; typedef long long ll; ll road[2501][2501]; int main() { int n, m, s, t; bool visit[2501]; ll best[2501] = { 0 }; for (int i = 0; i <= 2500; i++) for (int j = 0; j <= 2500; j++) road[i][j] = 1e18; for (int i = 0; i <= 2500; i++) best[i] = 1e18; cin >> n >> m >> s >> t; best[s] = 0; while (m--) { int a, b; ll c; cin >> a >> b >> c; if (c<road[a][b]) road[a][b] = road[b][a] = c; } while (1) { int ma = 1e18, target = -1; for (int i = 1; i <= n; i++) { if (!visit[i] && ma>best[i]) { ma = best[i]; target = i; } } if (target == -1)break; visit[target] = 1; for (int i = 1; i <= n; i++) { if (!visit[i]) { best[i] = min(best[i], best[target] + road[target][i]); } } } cout << best[t];//output return 0; }在不使用stl容器的前提下对这个代码进行优化和降重

可以考虑使用结构体数组代替二维数组表示边，减少空间占用。同时可以将输入和初始化操作合并，减少循环次数。代码如下：

#include <iostream>
#include <cstring>
#define N 25005
#define INF 1e18
using namespace std;
typedef long long ll;

struct Edge {
    int u, v;
    ll w;
} edge[N];

bool cmp(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

int n, m, s, t;
bool visit[2501];
ll best[2501];

int main() {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }

    sort(edge + 1, edge + m + 1, cmp);

    memset(best, 0x3f, sizeof(best));
    best[s] = 0;

    for (int i = 1; i <= m; i++) {
        int u = edge[i].u, v = edge[i].v;
        ll w = edge[i].w;
        if (w >= best[v]) continue;
        if (w + best[u] < best[v]) {
            best[v] = w + best[u];
        }
    }

    cout << best[t] << endl;

    return 0;
}

其中，cmp函数用于结构体数组的排序，memset函数用于初始化best数组。优化后的代码更加简洁，同时时间复杂度也有所降低。