C++ 代码
#include<iostream>
#include<memory.h>
#include<queue>
#include<vector>
#include<stdio.h>
using namespace std;
const int N = 5010;
const int M = 2e5;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int h[M], e[M], w[M], ne[M];
int dist[N][2];
int idx = 0;
long long int dp[N][2];
void add(int from, int to, int weight) {
e[idx] = to;
ne[idx] = h[from];
w[idx] = weight;
h[from] = idx++;
}
void dijkstra(int start) {
priority_queue<PII, vector<PII>, greater<PII>> q;
memset(dist, 0x3f, sizeof(dist));
q.push({ 0,start });
dist[start][0] = 0;
while (!q.empty()) {
PII front = q.top();
q.pop();
int u = front.second;
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
int distv = dist[u][0] + w[i];
int distv2 = dist[u][1] + w[i];
//if(dist[v][0] > distv) dp[v][0] += dp[u][0];
if (dist[v][1] > distv && dist[v][0] < distv) {
dist[v][1] = distv;
q.push({ dist[v][1],v });
// dp[v][1] += dp[u][0];
}
if (dist[v][1] > distv2 && dist[v][0] < distv2) {
dist[v][1] = distv2;
//dp[v][1] += dp[u][1];
q.push({ dist[v][1],v });
}
if (dist[v][0] > distv) {
dist[v][0] = distv;
q.push({ dist[v][0],v });
}
}
}
}
int main() {
memset(h, -1, sizeof(h));
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int a, b, l;
cin >> a >> b >> l;
add(a, b, l);
add(b, a, l);
}
dijkstra(1);
cout << dist[n][1] << endl;
return 0;
}