C++实现dijkstra单源最短路径算法-邻接表+优先队列

dijkstra单源最短路径算法不允许边权值为负，适用的图范围可以很大。

代码如下：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
const int N = 1e8;
bool done[N];
int dis[N];
const int INF = 1 << 30;
int n, m;

struct edge {
	int from;
	int to;
	int w;
};
vector<edge>e[N];

struct node {
	int id;
	int dis;
	friend bool operator<(const node &a, const node &b) {
		return a.dis > b.dis;
	}
};

void dijkstra(int s) //s为起点
{
	priority_queue<node>q;
	memset(done, 0, sizeof(done));
	for (int i = 1; i <= n; i++)
		dis[i] = INF;
	memset(done, 0, sizeof(done));
	dis[s] = 0;
	q.push({s, dis[s]});
	while (q.size()) {
		node t = q.top();
		q.pop();
		if (done[t.id])
			continue;
		done[t.id] = true;
		for (int i = 0; i < e[t.id].size(); i++) {
			edge y = e[t.id][i];
			if (done[y.to])
				continue;
			if (dis[y.to] > y.w + t.dis) {
				dis[y.to] = y.w + t.dis;
				q.push({y.to, dis[y.to]});
			}
		}
	}
}

int main() {
	while (cin >> n >> m, n, m) {
		for (int i = 1; i <= n; i++)
			e[i].clear();
		while (m--) {
			int a, b, c;
			cin >> a >> b >> c;
			e[a].push_back({a, b, c});
			e[b].push_back({b, a, c});
		}
		int start;
		cin >> start;//起点
		dijkstra(start);
		int no;
		while (cin >> no, no)//询问no点到起点的距离
		 {
			cout << dis[no] << endl;
		}
	}
	return 0;
}