小记: 在提交的时候 提交了4次,第一次有一句代码没删 RE,第二次 70分,边数又开小了忘记乘以10,第三次,最短距离数组的初始化赋值太小了,唉~ 真是差劲,一路下来,一个感觉秒过的题,历经了波澜曲折,汲取经验,下次不再重犯。
思路:spfa,单源最短路径算法,采取队列维护,这里没有优化,spfa的详细讲解:nocow
一、从起点开始更新与其相连的点的最短距离数组值,更新了的,没有入队的就入队。
二、从队列取队首的节点,然后更新其相连的点的权值,若是能更新,则看其是否已入队,没入队则入队
三、继续第二步。直至队空。
四、返回答案
优化策略:
SLF:Small Label First 策略。
实现方法是,设队首元素为 i,队列中要加入节点 j,在 d[i]<=d[j] 时加到队首而不是队尾,否则和普通的 SPFA 一样加到队尾。
LLL:Large Label Last 策略。
实现方法是,设队列 Q 中的队首元素为i,距离标号的平均值为 d_=(Vj属于Q,所有d[j]值的和,除以Q里元素的个数),每次出队时,若 d[i]>平均值,把 i 移到队列末尾,如此反复,直到找到一个 i 使 d[i]>=平均值,将其出队。
spfa可以判负环。对某点入队的次数进行判定,若大于节点数就存在负环。
O(Ke)k通常情况下不大于2,e为边数
这里代码是使用邻接表的数组形式实现的,因为n,m的数量级太大所以不能用邻接矩阵形式。 数组实现的邻接表 和 前向星 很相似
代码:
//#pragma comment(linker, "/STACK:102400000,102400000") #include <string.h> #include <stdio.h> #include <iostream> #include <vector> #include <queue> using namespace std; #define MAX_ 20010 #define MAX 0x7fffffff #define max(a,b) ((a>b)?(a):(b)) struct point { int v,cap,next; } edge[MAX_*10]; int head[MAX_]; int d[MAX_]; bool vis[MAX_]; int M, n, m; void add(int from, int to, int cap) { edge[M].v = to; edge[M].cap = cap; edge[M].next = head[from]; head[from] = M++; } void spfa(int start){ queue<int>q; for(int i = 0; i <= n; ++i){ d[i] = MAX; vis[i] = 0; } q.push(start); d[start] = 0; vis[start] = 1; while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = head[x]; i != -1; i = edge[i].next){ int v = edge[i].v; if(d[v] > d[x] + edge[i].cap){ d[v] = d[x] + edge[i].cap; if(!vis[v]){ vis[v] = 1; q.push(v); } } } } } int main() { int i; int s,t,c; while(~scanf("%d%d",&n,&m)) { M = 0; memset(head,-1,sizeof(head)); for(i = 0; i < m; i++) { scanf("%d%d%d",&s,&t,&c); add(s,t,c); } spfa(1); for(i = 2; i <= n; ++i){ printf("%d",d[i]); if(i!=n)printf("\n"); } } return 0; }