E - 最短路径·三：SPFA算法
题解
两端点之间可能存在多条路，需要找到最短路径。这里我用的是dijskra算法加上优先队列。
AC代码
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ull unsigned long long
#define ll long long
#define rep(i, x, y) for(int i=x;i<=y;i++)
#define mms(x, n) memset(x, n, sizeof(x))
#define mmc(a, b) memcpy(a, b, sizeof(b))
#define INF (0x3f3f3f3f)
#define mod (ull)(1e9+7)
typedef pair<int, int> P;
const int N = 1e5 + 10;
int n, m, s, t;
vector<P> G[N];
int d[N], vis[N];
void dij() {
fill(d, d + N, INF);
d[s] = 0;
priority_queue<P, vector<P>, greater<P> > q;
q.emplace(0, s);
while (!q.empty()) {
P x = q.top();
q.pop();
int l = x.first;
int v = x.second;
if (vis[v] == 1) continue;
vis[v] = 1;
for (int i = 0; i < G[v].size(); i++) {
P e = G[v][i];
int u = e.second;
int t = e.first;
if (d[u] > d[v] + t) {
d[u] = d[v] + t;
q.emplace(d[u], u);
}
}
}
}
int main() {
cin >> n >> m >> s >> t;
while (m--) {
int u, v, l;
cin >> u >> v >> l;
G[u].emplace_back(l, v);
G[v].emplace_back(l, u);
}
dij();
cout << d[t];
return 0;
}
