求最短路的算法只记得Floyd，单源最短路Dijstra差点忘了已经忘了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct Link{
	int from,to,dist;
};
struct Node{
	int d,u;
	bool operator <(const HeapNode & a) const{
		return d > a.d;
	}
};
struct SubstrateNetwork{
	int nodes;
	int links
	vector<Link> maplinks;
	bool isvisited[nodes+1];
	vector<int> G[nodes+1];
	int distance[nodes+1];
	int p[nodes+1];
	void init(int n){
		this->n = n;
		for(int i = 0;i <= n;i++)	G[i].clear();
		memset(vis,false,sizeof vis);
		for(int i = 0;i <= n;i++)	p[i] = i;
		for(int i = 1;i <= n;i++)	d[i] = INF;
	}
	void dijstra(int s){
		priority_queue<Node> q;
		q.push(Node{0,s});
		distance[s] = 0;
		while(!q.empty()){
			Node temp = q.top();
			q.pop();
			int u = temp.u;
			if(isvisited[u])
				continue;
			isvisited[u]=true;
			for(int i=0;i<G[u].size();i++){
				Link e = maplinks[G[u][i]];
				if(distance[e.to] > distance[u] + e.dist){
					distance[e.to] = distance[u] + e.dist;
					p[e.to] = u;
					q.push(HeapNode{distance[e.to],e.to});
				}			
			}
		}
	}
}