此题是经典的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; }