Til the Cows Come Home 最短路Dijkstra+bellman（普通+优化）
贝西在田里，想在农夫约翰叫醒她早上挤奶之前回到谷仓尽可能多地睡一觉。贝西需要她的美梦，所以她想尽快回来。
农场主约翰的田里有n（2<=n<=1000）个地标，唯一编号为1..n。地标1是谷仓；贝西整天站在其中的苹果树林是地标n。奶牛在田里行走时使用地标间不同长度的T（1<=t<=2000）双向牛道。贝西对自己的导航能力没有信心，所以一旦开始，她总是沿着一条从开始到结束的路线行进。
根据地标之间的轨迹，确定贝西返回谷仓必须走的最小距离。这样的路线一定存在。
解题思路
这个题是很典型的最短路问题，并且给了起点和终点，所以使用Dijkstra算法来解决单源最短路问题。
Dijkstra算法我这有两种形式，一种是普通的邻接矩阵法，复杂度是(O(n^2))，n是顶点的个数
然而使用邻接表和优先队列的形式，可以将复杂度优化到(O(m*logn))，m是边的个数，但是这种一般适用于稀疏图，对于稠密图，这种优化算法可能比原来没有优化的复杂度还要高。参考《算法竞赛入门经典（第二版）》360页。
这个题也可以用Bellman算法来进行实现。
代码实现
//普通的临界矩阵算法 dijkstra算法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;
int mp[maxn][maxn];
int dis[maxn];
int vis[maxn];
int t, n;
void dij()
{
for(int i=1; i<=n; i++)
{
dis[i]=mp[1][i];
}
vis[1]=1;
for(int i=1; i<n; i++)
{
int tmp=inf, k;
for(int j=1; j<=n; j++)
{
if(!vis[j] && dis[j]<tmp)
{
tmp=dis[j];
k=j;
}
}
vis[k]=1;
for(int j=1; j<=n; j++)
{
if(!vis[j] && dis[j] > dis[k]+mp[k][j])
dis[j]=dis[k] + mp[k][j];
}
}
}
void init()
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(i!=j) mp[i][j]=inf;
else mp[i][j]=0;
}
}
fill(vis+1, vis+n+1, 0);
fill(dis+1, dis+n+1, inf);
}
int main()
{
while(scanf("%d%d", &t, &n)!=EOF)
{
int a, b, c;
init();
for(int i=1; i<=t; i++)
{
scanf("%d%d%d", &a, &b, &c);
if(c < mp[a][b])
{
mp[a][b]=c;
mp[b][a]=c;
}
}
dij();
printf("%d
", dis[n]);
}
return 0;
}
优化的Dijkstra算法
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1e3+7;
const int maxe=2e3+7;
const int inf=0x3f3f3f3f;
struct edge{
int to, cost;
};
struct headnode{
int d, u;
bool friend operator < (const headnode a, const headnode b)
{
return a.d > b.d; //使用大于号是因为在优先队列中默认是从大到小的，这里需要反过来，从小到大。
}
};
int dis[maxn];
int vis[maxn];
vector<edge> g[maxn];
priority_queue<headnode> que;
int t, n;
void init()
{
for(int i=1; i<=n; i++)
{
g[i].clear();
vis[i]=0;
dis[i]=inf;
}
while(!que.empty()) que.pop();
}
void dij(int s)
{
int u;
edge e;
dis[s]=0;
headnode tmp={0, s};
headnode next;
que.push(tmp);
while(!que.empty())
{
tmp=que.top();
que.pop();
u=tmp.u;
if(vis[u]==1) continue;
vis[u]=1;
for(int i=0; i<g[u].size(); i++)
{
e=g[u][i];
if(dis[e.to] > dis[u]+e.cost)
{
dis[e.to]=dis[u]+e.cost;
next.d=dis[e.to];
next.u=e.to;
que.push(next);
}
}
}
}
int main()
{
while(scanf("%d%d", &t, &n)!=EOF)
{
init();
int a, b, c;
edge e;
for(int i=1; i<=t; i++)
{
scanf("%d%d%d", &a, &b, &c);
e.to=b;
e.cost=c;
g[a].push_back(e);
e.to=a;
e.cost=c;
g[b].push_back(e);
}
dij(1);
printf("%d
", dis[n]);
}
return 0;
}
Bellman算法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e3+7;
const int maxe=4e3+7; //这里一定要注意，t是路的条数，但是存图时每条路需要存储两遍。
const int inf=0x3f3f3f3f;
struct edge{
int a, b, c;
}e[maxe];
int dis[maxn];
int t, n, cnt; //
bool bellman(int s)
{
for(int i=1 ;i<=n; i++)
dis[i]=inf;
dis[s]=0;
bool flag;
int x, y, z;
for(int i=1; i<n; i++)
{
flag=false;
for(int j=1; j<cnt; j++)//cnt-1是边的条数
{
x=e[j].a;
y=e[j].b;
z=e[j].c;
if(dis[y] >= dis[x] + z)
{
dis[y]=dis[x]+z;
flag=true;
}
}
if(!flag)
break;
if(flag && i==n)
return false;
}
return true;
}
int main()
{
while(scanf("%d%d", &t, &n)!=EOF)
{
int a, b, c;
cnt=1;
for(int i=1; i<=t; i++)
{
scanf("%d%d%d", &a, &b, &c);
e[cnt].a=a; e[cnt].b=b; e[cnt++].c=c;
e[cnt].a=b; e[cnt].b=a; e[cnt++].c=c;
}
bellman(1);
printf("%d
", dis[n]);
}
return 0;
}
优化的Bellman算法，也就是鼎鼎大名的SPFA。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1e3+7;
const int inf=0x3f3f3f3f;
struct edge
{
int to, cost;
edge(){}
edge(int a, int b)
{
to=a;
cost=b;
}
};
int dis[maxn];
bool inq[maxn];
int cnt[maxn];
vector<edge> g[maxn];
queue<int>que;
int t, n;
bool spfa(int s)
{
for(int i=1; i<=n; i++)
{
dis[i]=inf;
inq[i]=false;
cnt[maxn]=0;
}
while(!que.empty()) que.pop();
edge e;
dis[s]=0;
inq[s]=true;
que.push(s);
while(!que.empty())
{
int u=que.front();
que.pop();
inq[u]=false;
for(int i=0; i<g[u].size() ; i++)
{
e=g[u][i];
if(dis[e.to] > dis[u]+e.cost)
{
dis[e.to] = dis[u]+e.cost;
if(inq[e.to]==false)
{
inq[e.to]=true;
que.push(e.to);
cnt[e.to]++;
if(cnt[e.to]>=n) return false; //这里是记录松弛的次数，如果达到n次说明有负环
}
}
}
}
return true;
}
int main()
{
while(scanf("%d%d", &t, &n)!=EOF)
{
int a, b, c;
for(int i=1; i<=n; i++)
g[i].clear();
for(int i=1; i<=t; i++)
{
scanf("%d%d%d", &a, &b, &c);
g[a].push_back(edge(b, c));
g[b].push_back(edge(a, c));
}
spfa(1);
printf("%d
", dis[n]);
}
return 0;
}