什么样的网站需要数据库,无锡建站模板系统,杭州seo网站推广,商城小程序哪家好题目#xff1a;样例#xff1a; 输入 6 6 0
0 1 2
0 2 5
0 3 1
2 3 2
1 2 1
4 5 1 输出 0 2 3 1 -1 -1 思路#xff1a; 根据题意#xff0c;数据范围也小#xff0c;也可以用朴素版的Dijsktra来做#xff0c;朴素版的Dijsktra我做过了一遍了#xff0c;可以看以一下我…题目样例
输入 6 6 0
0 1 2
0 2 5
0 3 1
2 3 2
1 2 1
4 5 1 输出 0 2 3 1 -1 -1 思路 根据题意数据范围也小也可以用朴素版的Dijsktra来做朴素版的Dijsktra我做过了一遍了可以看以一下我之前写的。 这次用堆优化有时候数据范围大那么一点点的时候比如数据范围是
的时候最坏情况下朴素版的Dijsktra的时间复杂度是1.5 * 10^5^2就会超时。
如果我们通过提前排序知道哪个路径是最短路的点即去掉一层循环时间复杂度就是1.5 * 10^5这样不会超时就需要用到 堆来排序我们每个点最短距离并且该点如果到达过就寻找下一个最短路径的由于数据范围较大用不了了邻接矩阵的方式我们只能用邻接表来实现了。
代码详解如下
#include iostream
#include cstring
#include algorithm
#include queue
#include unordered_map
#define endl \n
#define mk make_pair
#define x first
#define y second
#define int long long
#define YES puts(YES)
#define NO puts(NO)
#define umap unordered_map
#define INF 0x3f3f3f3f3f3f3f
#define All(x) (x).begin(),(x).end()
#pragma GCC optimize(3,Ofast,inline)
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N 2e6 10;// 存储 点与路径长度
using PII pairint,int;int n,m,s;int dist[N]; // 记录对应点的最短路
bool st[N]; // 标记该点是否走到过// 数组模拟邻接表更有效率
int h[N],e[N],w[N],ne[N],idx;
inline void Add(int a,int b,int c)
{e[idx] b,w[idx] c,ne[idx] h[a],h[a] idx;
}inline void Dijkstra()
{// 初始化 最短路memset(dist,INF,sizeof dist);// 初始化起点最短路距离是 0dist[s] 0;// 建立存储的 堆根据小根堆的 小到大排序priority_queuePII,vectorPII,greaterPIIq;// 这里小根堆的小到大排序规则// 所以我们需要距离小的排前面点放在后面q.push(mk(0,s));// 这里有一点点类似 BFS 做法while(q.size()){// 取出我们对应最短距离需要更新的堆组合auto now q.top();q.pop();int a now.y; // 取出对应的点int distence now.x; // 取出对应的最短距离if(st[a]) continue; // 如果我们点走动过就不用更新走动了st[a] true; // 标记当前走动更新的点// 更新该点的 distfor(int i h[a];i ! -1;i ne[i]){int j e[i]; // 取出对应点的关系// 如果该点j的距离 比 a 点到 j 点的距离还要大那么更新最短路径距离if(dist[j] distence w[i]) dist[j] distence w[i];// 存储对应距离和对应点方便下一次更新q.push(mk(dist[j],j));}}return ;
}inline void solve()
{// 链表初始化memset(h,-1,sizeof h);cin n m s;while(m--){int a,b,c;cin a b c;// 添加链表记录两点之间的距离Add(a,b,c);Add(b,a,c);}// 求最短路Dijkstra();// 输出各点的所得最短距离for(int i 0;i n;i){if(i)cout ;if(dist[i] INF) cout -1;else cout dist[i];}
}signed main()
{
// freopen(a.txt, r, stdin);___G;int _t 1;
// cin _t;while (_t--){solve();}return 0;
}
最后提交
