Dijkstra算法代码

随便记一下

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

//2021-3-19 11:31
//Dijkstra算法求单源最短路径

const int MAXN = 200;
const int INF = INT_MAX;

struct Edge {
    int to;     //边终点
    int length;     //边长度
    Edge(int t, int l) : to(t), length(l) {}
};

struct Point {
    int number;     //点编号
    int distance;       //源点到该点距离
    Point(int n, int d) : number(n), distance(d) {}
    bool operator< (const Point& p) const {
        return distance > p.distance;
    }
};

vector<Edge> graph[MAXN];
int dis[MAXN];

void Dijkstra(int s) {
    dis[s] = 0;
    priority_queue<Point> mypriorityqueue;
    mypriorityqueue.push(Point(s, dis[s]));
    while (!mypriorityqueue.empty()) {
        int u = mypriorityqueue.top().number;
        mypriorityqueue.pop();
        for (int i = 0; i < graph[u].size(); ++i) {
            int v = graph[u][i].to;
            int d = graph[u][i].length;
            if (dis[v] > dis[u] + d) {
                dis[v] = dis[u] + d;
                mypriorityqueue.push(Point(v, dis[v]));
            }
        }
    }
    return;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(graph, 0, sizeof(graph));
        fill(dis, dis + n, INF);
        while (m--) {
            int from, to, length;
            scanf("%d%d%d", &from, &to, &length);
            graph[from].push_back(Edge(to, length));
            graph[to].push_back(Edge(from, length));
        }
        int s, t;
        scanf("%d%d", &s, &t);
        Dijkstra(s);
        if (dis[t] == INF) {
            dis[t] = -1;
        }
        printf("%d\n", dis[t]);
    }
    return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议