51nod_1459 最短路 dijkstra 特调参数

好多基础知识都没补完，只好看到、用到一个赶紧补全一个，并且保证下次需要的时候直接用，不用回来再补；

其实这个算法是在补同余最短路的时候用到的，当时突然发现理解算法导论上的原理甚至有效性证明，但是就是没办法写出来合适的代码。。于是到处寻找可以用来试验最短路径算法的试验场（当时学矩阵快速米的时候也是找了51nod上面的一到基础题作为测试的）来熟悉和不全最短路相关基础知识。

首先是DIJKSTRA

对于DIJKSTRA首先是个贪心算法，每次从集合中选择一条没有走过的最短路径来作为新的边，到达新的节点。在以当前找到的这条边更新所有可达的边——所谓的松弛操作。

可以证明，在n次这样的松弛操作之后，可以求得单元最短路（具体证明见算法导论）

这题的要求比单元最短路相对更高些，他要求找到最短路且权重最高的路径。因而应当在每次进行松弛操作时进行更新——当且仅当路径长度相同时选择更大的权重，其他时候选择更短的边的权重。

DIJKSTRA如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const long long INF=1e12+233;
 5 const long long MAXN=1e3+233;
 6 long long dp[MAXN];
 7 long long point[MAXN];
 8 long long mon[MAXN];
 9 long long path[MAXN][MAXN];
10 long long n,m,start,end;
11 
12 void init()
13 {
14     cin>>n>>m>>start>>end;
15     memset(mon,0,sizeof(mon));
16     for(int i=0;i<MAXN;++i)
17         for(int j=0;j<MAXN;++j)path[i][j]=INF;
18     for(int i=0;i<n;++i)
19     {
20         cin>>point[i];
21         dp[i]=INF;
22     }
23     for(int i=0;i<m;++i)
24     {
25         int a,b,p;
26         cin>>a>>b>>p;
27         path[a][b]=p;
28         path[b][a]=p;
29     }
30 }
31 int v[MAXN];
32 void dijkstra()
33 {
34     memset(v,0,sizeof(v));
35     int x=start;
36     mon[start]=point[start];
37     dp[start]=0;        //dijkstra初始化，应当以最起始点为0点
38     for(int i=0;i<n;++i)
39     {
40         long long mini=INF;
41         for(int j=0;j<n;++j)
42         {
43             if(!v[j]&&dp[j]<mini)
44             {
45                 x=j;
46                 mini=dp[j];
47             }
48         }v[x]=1;        //标记出现过的点
49         for(int j=0;j<n;++j)
50         {
51             if(!v[j]&&dp[j]>dp[x]+path[x][j])
52             {
53             
54                 mon[j]=mon[x]+point[j];
55             }if(!v[j]&&dp[j]==dp[x]+path[x][j])//注意更新时确保该点没有被走到，否则可能出现重复更新
56             {
57                 mon[j]=max(mon[j],mon[x]+point[j]);
58             }
59             
60             dp[j]=min(dp[x]+path[x][j],dp[j]);
61         }
62     }cout<<dp[end]<<" "<<mon[end]<<endl;
63 }
64 int main()
65 {
66     cin.sync_with_stdio(false);
67     init();
68     dijkstra();
69     return 0;
70 }

堆优化的dijkstra，来自刘汝佳的蓝书，同样要注意简要修改下。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 const long long MAXN=500+233;
  5 const long long INF=1e7+2;
  6 
  7 
  8 
  9 class Edge
 10 {
 11     public:
 12         long long from,to,dist;
 13 };
 14 
 15 
 16 class HeapNode
 17 {
 18     public:
 19         long long d,u;
 20         bool operator < (const HeapNode& h1)const
 21         {
 22             return this->d>h1.d;
 23         }
 24 };
 25 
 26 long long mon[MAXN];
 27 long long point[MAXN];
 28 long long n1,m1,start,end;
 29 
 30 struct Dijkstra
 31 {
 32     long long n,m;
 33     vector<Edge> edges;
 34     vector<long long> G[MAXN];
 35     bool done[MAXN];
 36     long long d[MAXN];
 37     long long p[MAXN];
 38     
 39     void init(long long n)
 40     {
 41         this->n=n;
 42         for(long long i=0;i<n;++i)
 43         {
 44             G[i].clear();
 45         }edges.clear();
 46     }
 47     
 48     void AddEdge(long long from,long long to,long long dist)
 49     {
 50         edges.push_back((Edge){from,to,dist});
 51         m=edges.size();
 52         G[from].push_back(m-1);
 53     }
 54     
 55     void dijkstra(long long s)
 56     {
 57         priority_queue<HeapNode> Q;
 58         for(long long i=0;i<n;++i)d[i]=INF;
 59         d[s]=0;
 60         memset(done,0,sizeof(done));
 61         Q.push((HeapNode){0,s});
 62         mon[s]=point[s];
 63         while(!Q.empty())
 64         {
 65             HeapNode x=Q.top();Q.pop();
 66             long long u=x.u;
 67             if(done[u])continue;
 68             done[u]=true;
 69             for(long long i=0;i<G[u].size();++i)
 70             {
 71                 Edge &e=edges[G[u][i]];
 72                 if(d[e.to]>d[u]+e.dist)
 73                 {
 74                     d[e.to]=d[u]+e.dist;
 75                     p[e.to]=G[u][i];
 76                     Q.push((HeapNode){d[e.to],e.to});
 77                     mon[e.to]=mon[u]+point[e.to];
 78                 }else if(d[e.to]==d[u]+e.dist)
 79                 mon[e.to]=max(mon[u]+point[e.to],mon[e.to]);
 80             }
 81         }
 82     }
 83 };
 84 
 85 int main()
 86 {
 87     cin.sync_with_stdio(false);
 88     Dijkstra d1;
 89     cin>>n1>>m1>>start>>end;
 90     for(long long i=0;i<n1;++i)cin>>point[i];
 91     d1.init(n1);
 92     for(long long i=0;i<m1;++i)
 93     {
 94         long long a,b,p;cin>>a>>b>>p;
 95         d1.AddEdge(a,b,p);
 96         d1.AddEdge(b,a,p);
 97     }
 98     d1.dijkstra(start);
 99     
100     cout<<d1.d[end]<<" "<<mon[end]<<endl;
101     
102     
103     
104     return 0;
105 }

Bellman_Ford算法：
首先，算法思路：设定某有向图中，不存在负环，则对于每条最短路，都会在每一轮松弛中，得到至少一条最短路。

若有向图G中，有一条最短路：A->B->C->D->E，那么因为起始节点为A，则A->B的最短路径会在第一轮松弛操作时被找到。而后操作也是同理。接下来的每个最短路元素都会在未来的某一次松弛操作中被找到。因为每轮松弛操作都至少找到一个元素，所以我们应当认为