次短路草稿

本文主要是介绍次短路草稿，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

草稿草稿
原题链接

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
struct edge {int v, w;
};
struct node {int u, d;bool operator < (const node& x)const {return x.d < d;}
};
vector<edge>g[200000];
int dis[120000], dis1[120000];
int n, m;
void dij()
{priority_queue<node> q;q.push({ 1,0 });dis[1] = 0;while (!q.empty()){node nd = q.top(); q.pop();int u = nd.u;for (int i = 0; i < g[u].size(); ++i){int v = g[u][i].v, w = g[u][i].w;int f = 0;if (dis[v] > w + dis[u]){f = 1;dis1[v] = dis[v];dis[v] = w + dis[u];}if (dis[v] < w + dis[u] && dis1[v] > w + dis[u]){f = 1;dis1[v] = w + dis[u];}if (dis1[v] > dis1[u] + w){f = 1;dis1[v] = dis1[u] + w;}if (f)q.push({ v,dis[v] });}}}
int main()
{scanf("%d%d", &n, &m);for (int i = 0; i <= n; ++i){g[i].clear();dis[i] = dis1[i] = 0x3f3f3f3f;}for (int i = 0; i < m; ++i){int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a].push_back({ b,c });g[b].push_back({ a,c });}dij();cout << dis1[n];return 0;
}

这篇关于次短路草稿的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---