C++(g++ 7.5.0) 解法, 执行用时: 36ms, 内存消耗: 2928K, 提交时间: 2023-08-10 17:27:36

#include<bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N = 5e3 + 10 , M = 1e5 + 10;
int h[N],e[M<<1],nxt[M<<1],w[M<<1];
int dis[N][2];
bool st[N][2];
int tot;
int n,m;
int u,v,s;
inline void add(int u,int v,int s) {
    e[++tot] = v;
    nxt[tot] = h[u];
    h[u] = tot;
    w[tot] = s;
}
inline void spfa() {
    memset(dis,0x3f,sizeof dis);
    memset(st,false,sizeof st);
    queue<PII> q;
    dis[1][0] = 0;
    q.push({1,0});
    while(q.size()) {
        auto t = q.front();
        q.pop();
        st[t.x][t.y] = false;
        for(int i = h[t.x];~i;i = nxt[i]) {
            int to = e[i];
            int d = dis[t.x][t.y] + w[i];
            if(dis[to][0] > d) {
                dis[to][1] = dis[to][0];
                dis[to][0] = d;
                if(!st[to][0]) {
                    st[to][0] = true;
                    q.push({to,0});
                }
                if(!st[to][1]) {
                    st[to][1] = true;
                    q.push({to,1});
                }
            } else if(dis[to][1] > d && dis[to][0] < d) {
                dis[to][1] = d;
                if(!st[to][1]) {
                    st[to][1] = true;
                    q.push({to,1});
                }
            }
        }
    }
}
int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--) {
        cin>>u>>v>>s;
        add(u,v,s),add(v,u,s);
    }
    spfa();
    printf("%d",dis[n][1]);
    
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 115ms, 内存消耗: 3544K, 提交时间: 2019-12-28 20:29:36

#include <bits/stdc++.h>
using namespace std;

struct Edge {
  int u, v, w;
};


int main() {
  int N, R; cin >> N >> R;
  vector<Edge> edges;
  while (R--) {
    int A, B, D; cin >> A >> B >> D;
    edges.push_back(Edge{A, B, D});
    edges.push_back(Edge{B, A, D});
  }
  vector<vector<int>> D(N+1, vector<int>(2, 0x3f3f3f3f));
  D[1][0] = 0;
  for (int i = 1; i <= 2 * N; i++) {
    // for (int i = 1; i <= N; i++) cout << D[i][0] << " "; cout << endl;
    // for (int i = 1; i <= N; i++) cout << D[i][1] << " "; cout << endl;
    bool ok = true;
    for (auto e: edges) {
      if (D[e.v][0] > D[e.u][0] + e.w) {
        D[e.v][1] = D[e.v][0];
        D[e.v][0] = D[e.u][0] + e.w;
        ok = false;
      } else if (D[e.v][0] != D[e.u][0] + e.w && D[e.v][1] > D[e.u][0] + e.w) {
        D[e.v][1] = D[e.u][0] + e.w;
        ok = false;
      } 
      if (D[e.v][1] > D[e.u][1] + e.w) {
        D[e.v][1] = D[e.u][1] + e.w;
        ok = false;
      }
    }
    if (ok) break;
  }
  cout << D[N][1] << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 128ms, 内存消耗: 3672K, 提交时间: 2020-05-21 11:44:27

#include<bits/stdc++.h>
using namespace std;
struct Edge
{
    int u,v,w;
};
int main()
{
    int N,R;
    cin>>N>>R;
    vector<Edge> edges;
    while(R--)
    {
        int A,B,D;
        cin>>A>>B>>D;
        edges.push_back(Edge{A,B,D});
        edges.push_back(Edge{B,A,D});
    }
    vector<vector<int> > D(N+1,vector<int>(2,0x3f3f3f3f));
    D[1][0]=0;
    for(int i=1;i<=2*N;i++)
    {
        bool ok=true;
        for(auto e:edges)
        {
            if(D[e.v][0]>D[e.u][0]+e.w)
            {
                D[e.v][1]=D[e.v][0];
                D[e.v][0]=D[e.u][0]+e.w;
                ok=false;
            }
            else if(D[e.v][0]!=D[e.u][0]+e.w&&D[e.v][1]>D[e.u][0]+e.w)
            {
                D[e.v][1]=D[e.u][0]+e.w;
                ok=false;
            }
            if(D[e.v][1]>D[e.u][1]+e.w)
            {
                D[e.v][1]=D[e.u][1]+e.w;
                ok=false;
            }
        }
        if(ok)
        break;
    }
    cout<<D[N][1]<<endl;
}