数据结构图 Dijkstra算法

ゝ一世哀愁。 2022-06-09 04:24 235阅读 0赞

#include <cstdio>
    #include <queue>
    #include <vector>
    #include <iostream>
    #include <cstring>
    using namespace std;
    const int maxn = 1024;
    const int INF = 0x7fffffff;
    typedef pair<int, int> P;  //到这个点的最短路长度  和这个点
    int ans;
    struct edge  //边的终点 和长度
    {
        int to, cost;
    };
    
    int V;
    vector<edge> G[maxn];
    int d[maxn];  //原点到某个点的最短路的长度
    
    int  dijkstra(int s)
    {
        priority_queue<P, vector<P>, greater<P> > que;  //用来动态的寻找每次权值最小的路和点 队列中元素从小到大排序
        for(int i=0;i<maxn;i++) d[i]=INF;
        d[s] = 0;
        que.push(P(0, s));
        while (!que.empty())
        {
            P p = que.top();    //每次确定的标为*的点（不改变的点）
            que.pop();
            int v = p.second;
             if(d[v] < p.first) continue;  //到v点的距离如果已经被更新 这无须执行以下操作
            for (int i = 0; i < G[v].size(); ++i)  //找出与这个点相连的边
            {
                edge e= G[v][i];
                if (d[e.to] > d[v] +e.cost)
                {
                    d[e.to] = d[v] + e.cost;
                    if(e.cost > ans )  ans=e.cost;
                    que.push(P(d[e.to], e.to));  //将更新后的点放进去
                }
            }
        }
        cout<<ans<<endl;
        printf("%d\n",d[1]);
        return 0;
    }
    int main()
    {
        int m;
        while(scanf("%d%d",&V,&m)!=EOF)
        {
    
            for (int i = 0; i < V; ++i)
            {
                int from, to, cost;
                scanf("%d%d%d", &from, &to, &cost);
                edge point;
               //利用队列把图连接起来
                point.to=to;
                point.cost=cost;
                G[from].push_back(point);
                point.to=from;
                G[to].push_back(point);
            }
            ans=0;
            dijkstra(m);
    
        }
    
        return 0;
    }