【蓝桥杯】最短路

调用的spfa算法，至于神马堆优化的disk算法，表示弱渣完全不理解的说。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int maxn = 20010;
const int maxm = 200010;
const int inf = 200000;

int head[maxn], dist[maxn]; //head数组记录以i为顶点的上一条边的存储位置，若是第一次出现，记录为-1 
int n, m;
struct node {
	int to;
	int w;
	int next;
}edges[maxm];
queue<int> q; 

void spfa(int s) {
	bool vis[maxn];
	for(int i = 0; i <= n; i++) {
		dist[i] = inf;  //将路都设为一个极值，方便比较和更新 
	}
	memset(vis, false, sizeof(vis));
	dist[s] = 0;  //因为不存在环,故从s到s的距离肯定为0
	vis[s] = true; 
	q.push(s);
	while( !q.empty() ) {
		int top = q.front();
		vis[top] = false; //从顶点top开始,并把点top的vis重新清空为-1
		int k = head[top]; //k记录从顶点top出发最后一个结点
		while( k >= 0 ) {  //若k >= 0 则表示从点top开始还有边 
			if( dist[ edges[k].to ] > edges[k].w + dist[top] ) { //如果点top到点edges[k].to的距离小于dist[ edges[k].to ] 
				dist[ edges[k].to ] = edges[k].w + dist[top];
				if( !vis[ edges[k].to ] ) {  //如果该点没有被标记过 
					q.push(edges[k].to);     //进入队列 
					vis[ edges[k].to ] = true; //表示该点已经标记过，避免重复访问 
				}
			}
			k = edges[k].next;  //更新从top开始的下一条边的位置 
		} 
		q.pop();
	} 
}

int main() {
	int u, v, l;  //u是起点, v是终点, l是路径长度 
	scanf("%d%d", &n, &m);
	memset(head, -1, sizeof(head)); //把数组head的值全都填充为-1  
	for(int i = 0; i < m; i++) {
		scanf("%d%d%d", &u, &v, &l);
		edges[i].to = v;  //to表示下一个结点的位置
		edges[i].w = l;   //w记录路径长度
		edges[i].next = head[u]; //next用于记录上一次 点u出现的数组位置 
		head[u] = i;      //更新点u这次的出现位置 
	}
	spfa(1);
	for(int i = 2; i <= n; i++) {
		cout << dist[i] << endl;
	}
	return 0;
}

数据结构用的是传说中的：链式前向星

附带讲解地址：

http://blog.sina.com.cn/s/blog_6ae8849b0100srlt.html

http://malash.me/200910/linked-forward-star/

说实话自己理解的还是太过模糊，等日后理解透彻或许会写一篇链式前向星的讲解。。。。

秒客网

【蓝桥杯】最短路

相关文章