最短路径专题总结

一.模板：

1.dijsktra算法（矩阵）：

 1 int n,cost[1005][1005],dis[1005],vis[1005],dp[1005];  
 2 void dijkstra(int st)
 3 {
 4     memset(vis,0,sizeof(vis));
 5     for(int i = 1; i<=n; i++)
 6         dis[i] = (i==st?0:INF);
 7 
 8     for(int i = 1; i<=n; i++)
 9     {
10         int k, minn = INF;
11         for(int j = 1; j<=n; j++)
12             if(!vis[j]&&dis[j]<minn)
13                 minn = dis[k=j];
14 
15         vis[k] = 1;
16         for(int j = 1; j<=n; j++)
17             if(!vis[j] && cost[k][j]!=INF)        
18                 dis[j] = min(dis[j], dis[k] + cost[k][j]);
19     }
20 }

View Code

2.dijsktra算法（前向星）：

 1 struct edge
 2 {
 3     int to, w, next;
 4 }edge[maxn*maxn];
 5 int cnt, head[maxn];
 6 
 7 void addedge(int u, int v, int w)
 8 {
 9     edge[cnt].to = v;
10     edge[cnt].w = w;
11     edge[cnt].next = head[u];
12     head[u] = cnt++;
13 }
14 
15 void init()
16 {
17     cnt = 0;
18     memset(head, -1, sizeof(head));
19 }
20 
21 int dis[maxn], vis[maxn];
22 void dijkstra(int st)
23 {
24     memset(vis, 0, sizeof(vis));
25     for(int i = 1; i<=n; i++)
26         dis[i] = (i==st?0:INF);
27 
28     for(int i = 1; i<=n; i++)
29     {
30         int k, minn = INF;
31         for(int j = 1; j<=n; j++)
32             if(!vis[j] && dis[j]<minn)
33                 minn = dis[k=j];
34 
35         vis[k] = 1;
36         for(int j = head[k]; j!=-1; j = edge[j].next)
37             if(!vis[edge[j].to])
38                 dis[edge[j].to] = min(dis[edge[j].to], dis[k] + edge[j].w);
39     }
40 }

View Code

3.bellman-ford算法（前向星）：

 1 struct edge
 2 {
 3     int u, v, w;
 4 }edge[maxn*maxn];
 5 int cnt;
 6 
 7 void addedge(int u, int v, int w)
 8 {
 9     ++cnt;
10     edge[cnt].u = u;
11     edge[cnt].v = v;
12     edge[cnt].w = w;
13 }
14 
15 int dis[maxn];
16 bool bellman(int st)
17 {
18     for(int i = 1; i<=n; i++)
19         dis[i] = (i==st?0:INF);
20 
21     for(int i = 1; i<=n-1; i++)
22     {
23         for(int j = 1; j<=cnt; j++)
24         {
25             int u = edge[j].u;
26             int v = edge[j].v;
27             if(dis[u]!=INF)
28                 dis[v] = min(dis[v], dis[u]+edge[j].w);
29         }
30     }
31 
32     for(int i = 1; i<=cnt; i++)    //判断是否存在负环
33     {
34         int u = edge[i].u;
35         int v = edge[i].v;
36         if(dis[u]!=INF && dis[u]+edge[i].w<dis[v])
37             return false;
38     }
39     return true;
40 }

View Code

4.spfa算法（前向星）：

 1 struct edge
 2 {
 3     int to, w, next;
 4 }edge[maxn*maxn];
 5 int cnt, head[maxn];
 6 
 7 void addedge(int u, int v, int w)
 8 {
 9     edge[cnt].to = v;
10     edge[cnt].w = w;
11     edge[cnt].next = head[u];
12     head[u] = cnt++;
13 }
14 
15 void init()
16 {
17     cnt = 0;
18     memset(head, -1, sizeof(head));
19 }
20 
21 int dis[maxn], times[maxn], inq[maxn];
22 bool spfa(int st)
23 {
24     memset(inq, 0, sizeof(inq));
25     memset(times, 0, sizeof(times));
26     for(int i = 1; i<=n; i++)
27         dis[i] = (i==st?0:INF);
28 
29     queue<int>Q;
30     Q.push(st);
31     inq[st] = 1;
32     while(!Q.empty())
33     {
34         int u = Q.front();
35         Q.pop(); inq[u] = 0;
36         for(int i = head[u]; i!=-1; i = edge[i].next)
37         {
38             int v = edge[i].to;
39             if(dis[v]>dis[u]+edge[i].w)
40             {
41                 dis[v] = dis[u]+edge[i].w;
42                 if(!inq[v])
43                 {
44                     Q.push(v);
45                     inq[v] = 1;
46                     if(++times[v]>n) return false;
47                 }
48             }
49         }
50     }
51     return true;
52 }

View Code

5.floyd算法：

1 for(int i = 1; i<=n; i++)    
2     for(int j = 1; j<=n; j++)    
3         scanf("%d",&dis[i][j]);    
4 
5 for(int k = 1; k<=n; k++)   
6     for(int i = 1; i<=n; i++)    
7         for(int j = 1; j<=n; j++)    
8             dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);

View Code

二.题目类型：

1.普通最短路：

POJ1511 Invitation Cards

POJ3268 Silver Cow Party

2.最短路变形：

POJ2253 Frogger

POJ1797 Heavy Transportation

CSU1808 地铁

3.求负环或正环：

POJ3259 Wormholes

POJ1860 Currency Exchange

4.传递闭包：

POJ3660 Cow Contest

5.差分约束：

POJ3159 Candies

最短路径 专题总结

最短路径专题总结