HDU 2544 最短路【Bellman

HDU 2544 最短路【Bellman_Ford 】

题意：给出n个节点，m条边，问从起点到终点的最短距离

用bellman_ford，注意是无向图

初学bellman_ford= =一点点理解

因为dijkstra是每次用集合里面的点去更新它们所连接的点的距离假设集合s={A},

如果B能够被A“带”入集合的话，说明AB一定是最短的距离了，因为后来不管怎么样，边权都是正的，不会使得AB变得更小

所以，dijkstra只能处理正权图

然后Bellman_Ford可以处理负权，反复用已有的边来更新最短距离

从起点1到终点n的最短距离最多经过n-2个点，即为最多松弛n-1次

如果第n次还能够松弛成功，说明含有负权回路

大概先理解了这些，优化再好好学= =证明也再好好看

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 #define mod=1e9+7;
12 using namespace std;
13 
14 typedef long long LL;
15 const int INF = 0x3f3f3f3f ;
16 const int maxn=10005;
17 int d[maxn];
18 
19 struct edge{
20     int u,v,w;
21 } e[maxn];
22 
23 int flag=1,nodenum,edgenum,st;
24 
25 void bellman_ford(){
26     int i,j,k;
27     for(i=1;i<=nodenum;i++)
28     d[i] = (i == st ? 0 : INF);
29     
30     for(i=1;i<nodenum;i++){
31         for(j=1;j<=2*edgenum;j++){
32             if(d[e[j].v]>d[e[j].u]+e[j].w) d[e[j].v]=d[e[j].u]+e[j].w;//松弛 
33         }
34     }  
35 }
36 
37 int main(){
38     int i,j,k,u,v,w;
39     while(scanf("%d %d",&nodenum,&edgenum)!=EOF&&nodenum&&edgenum){
40         for(i=1;i<=2*edgenum;i++){
41             scanf("%d %d %d",&u,&v,&w);//无向图 
42             e[i].u=u;e[i].v=v;e[i].w=w;
43             i++;
44             e[i].u=v;e[i].v=u;e[i].w=w;
45         }
46         
47         st=1;
48         
49         bellman_ford();
50         printf("%d
",d[nodenum]);
51     }
52     return 0;
53 }

View Code

加油 go---go--go