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