电子商务网站规划与.../营销策略国内外文献综述
问题描述
给定一个n个顶点，m条边的有向图(其中某些边权可能为负，但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。
输入格式
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式
共n-1行，第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
单源点最短路径
Bellman-Ford算法
知识点：
1.松弛操作
d[v]=min(d[v],d[u]+w[u,v])
不断降低原点到v点的最优值上界
2.松弛操作的性质
假设u到v的最短路是(u,X1,X2,......v)，对(u,X1)(X1,X2)...(Xn,v)依次(不必连续)进行松弛操作，最后可以得到d[v]
基本思路：
对于最坏情况，最短路有n-1个结点，所以要进行n-1次松弛
每次松弛顾及所有情况，所以每条边要松弛一下
时间复杂度O(E*V),对于这道题超时了。
代码如下：
#include#include#define INF 99999999
#define min(a,b) au=st;
poi->v=end;
poi->l=len;
poi->p=(struct edge*)malloc(sizeof(struct edge));
poi=poi->p;
}
for(i=1;i<=n;i++)
d[i]=INF;
d[1]=0;
for(i=1;iu]v]=min(d[poi->v],d[poi->u]+poi->l);
poi=poi->p;
}
for(i=2;i<=n;i++)
printf("%d\n",d[i]);
}
dijkstra算法
基本思路：每次找距离小的点，更新以它为起点的边的终点的距离值
主要操作：
1.储存图
链表
用head[结点]储存以某结点为起点的一条边的编号，再用next[边]储存与某边共起点的另一条边，也能用指针
vector
一个储存边结构，一个储存某个结点对应的边序号
2.更新d[结点]原点到结点距离
有两种，一个是普通的外层结点数次循环，内层遍历d[]找最小值，时间复杂度O(n^2)
还有一种需要使用优先队列，先用结构重新定义优先级，然后先放原点进去，遍历以原点为起点的边，松弛操作，其实就是把剩下
d存在的点放到队列里，原点出列，然后找d最小的点，。。。。。。。。
这里有两个问题
每次出列的是不是未标记的最小d的点？
每次更新后，d存在的点都放进了队列，剩下的都是无穷大。
会不会有重复结点出现？
如果以u为起点的边e，终点为v，然后更新后，又有一个v点放入，会出现重复，加一个done[]数组即可。
时间复杂度O(边数*log(结点数))，
AC代码
#include
#include #include#include #include#include#includeusing namespace std;
#define min(a,b) ((aedge;
vectorG[20010];
void build(){
int from,to,dist;
for(int i=0;iprio.d;
}
};
int done[20010]={0};
void dijkstra(int s){
for(int i=1;i<=n;i++)
d[i]=INF;
d[s]=0;
priority_queueq;
q.push((node){d[s],s});
while(!q.empty()){
node x=q.top();q.pop();
int u=x.u;
if(done[u])continue;
done[u]=1;
for(int i=0;id[u]+e.dist){
d[e.to]=d[u]+e.dist;
q.push((node){d[e.to],e.to});
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
build();
dijkstra(1);
for(int i=2;i<=n;i++)
printf("%d\n",d[i]);
return 0;}