HDU1874 - 畅通工程续

此题是经典的Dijkstra单源最短路径问题。

// runtime: 33ms
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MAX = 200;

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;
    }
};

int dis[MAX]; // 源点到各点的距离
vector<Edge> graph[MAX]; // 邻接表实现的图

void Dijkstra(int s) {
    dis[s] = 0;
    priority_queue<Point> q;
    q.push(Point(s, dis[s]));

    while (!q.empty()) {
        int n = q.top().number; // 离源点最近的点
        q.pop();

        for (int i = 0; i < graph[n].size(); ++i) {
            int to = graph[n][i].to;
            int len = graph[n][i].length;

            if (dis[to] > dis[n] + len) {
                dis[to] = dis[n] + len;
                q.push(Point(to, dis[to]));
            }
        }
    }
}

int main() {

    int n, m;
    while (cin >> n >> m) {

        memset(graph, 0, sizeof(graph));
        fill(dis, dis + n, INT_MAX); // 初始化为不可达

        while (m--) {
            int from, to, d;
            cin >> from >> to >> d;
            graph[from].push_back(Edge(to, d));
            graph[to].push_back(Edge(from, d));
        }
        int s, t;
        cin >> s >> t;

        Dijkstra(s);

        if (dis[t] == INT_MAX)
            cout << -1 << endl;
        else
            cout << dis[t] << endl;
    }
    return 0;
}