1.dijkstra（无法求负边） #include using namespace std; #define endl '\n' const int N = 3e5; int n, m, s, t; vector > g[N]; int dis[N]; int st[N]; void dij() { memset(dis,0x3f,sizeof(dis)); priority_queue,vector>,greater>> pq; pq.push({0,s}); while (pq.size()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (st[u])continue; st[u] = 1; for (auto i : g[u]) { int v = i.first; int w = i.second; if (dis[v] > d + w){ dis[v] = d + w; pq.push({dis[v],v}); } } } cout << dis[t]; } signed main() { std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t; for (int i = 0;i > u >> v >> w; g[u].push_back({v,w}); g[v].push_back({u,w}); } dij(); return 0; } 2.贝尔特佛特（可以求负边） int n, m; // n表示点数，m表示边数 int dist[N]; // dist[x]存储1到x的最短路距离 struct Edge // 边，a表示出点，b表示入点，w表示边的权重 { int a, b, w; }edges[M]; // 求1到n的最短路距离，如果无法从1走到n，则返回-1。 int bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。 for (int i = 0; i < n; i ++ ) { for (int j = 0; j < m; j ++ ) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[b] > dist[a] + w) dist[b] = dist[a] + w; } } if (dist[n] > 0x3f3f3f3f / 2) return -1; return dist[n]; } 3.Floyd（dp思想） for (k = 1; k <= n; k++) { for (x = 1; x <= n; x++) { for (y = 1; y <= n; y++) { f[x][y] = min(f[x][y], f[x][k] + f[k][y]); } } } 上述算法，dijkstra时间复杂度最低，Floyd最好n的三次方，但是可以求图上连通点之间的最短距离

数组离散化处理，本质哈希

全站热榜