Dijkstra算法堆优化(vector建图)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Dijkstra算法堆优化(vector建图)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含861字，纯文字阅读大概需要2分钟。

内容图文

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<queue>
#include <vector>
#include <map>
int s,t;
int n,m;
using namespace std;
const int INF=99999999;
struct Node{
    int to;
    int w;
};
struct Node temp;
vector<Node> v[1002];
typedef pair<int, int> P;
int dis[1002];
void Dijkstra(){
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    priority_queue<P,vector<P>,greater<P> >que;
    que.push(P(0,1));
    dis[1]=0;
    while(!que.empty()){
        P p=que.top();que.pop();
        if(dis[p.second]<p.first)
            continue;
        for(int i=0;i<v[p.second].size();i++){
            if(dis[v[p.second][i].to]>dis[p.second]+v[p.second][i].w){
                dis[v[p.second][i].to]=dis[p.second]+v[p.second][i].w;
                que.push(P(dis[v[p.second][i].to],v[p.second][i].to));
            }
        }
    }
}
 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        v[i].clear();
    for(int i=1;i<=m;i++){
            cin>>s>>temp.to>>temp.w;
            v[s].push_back(temp);
    }
    Dijkstra();
    cout<<dis[6];
    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的Dijkstra算法堆优化(vector建图)全部内容，希望文章能够帮你解决Dijkstra算法堆优化(vector建图)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---