Dijkstra算法用来计算图的单源最短路径,实际上就是两步:
图论中另一个求最小生成树的的经典算法Prim算法与Dij过程极其类似,都是贪心思想。只是一个是对顶点的选择,另外一个是对边的选择。
本质上Dijkstra是一个带贪心策略的广度优先搜索,此处的广度定义在路程的cost之上。
Dijkstra算法的分解思路是: 到达某节点的cost最小路径 --(从这里面选)--> { 到达其相邻节点的cost最小路径 } 独一选择性: 只挑选: Min {到达其相邻节点的最短路径}
http://acm.pku.edu.cn/JudgeOnline/problem?id=1062 题目是中文的大意就不用说了,从复杂的题目描述来看,要借助画图来更好地理解题意。画出图后发现其实就是一个最短路问题。用Dij解决,自己写了个以猷长为起点的Dij,无限WA,无奈到网上找了篇解题报告。发现向图中添加一个铺助起始点,可以很完美地解决问题。另外这题中加入了结点等级的限制,我们可以枚举最高等级,依据最高等级,确定能纳入最短路的结点的等级范围。至此,就完完全全的就是一个最短路了
#include<iostream>
#include<cmath>
using namespace std;
const int inf=0x7fffffff;
int M,N,dmax,dmin,tmin;
int c[105][105];
int degree[105];
int dist[105];
bool s[105],use[105];
bool In(int a)
{
return abs(dmax-a)<=M&&abs(dmin-a)<=M;
}
int dij()
{
int i,j,k;
for(i=0;i<=N;i++) {dist[i]=c[0][i];s[i]=0;}
s[0]=1;use[0]=1;
for(i=1;i<=N;i++)
{
tmin=inf;
for(j=1;j<=N;j++)//寻找当前未被纳入符合最短距离的结点
{
if(!s[j]&&use[j]&&tmin>dist[j])
{
k=j;
tmin=dist[j];
}
}
s[k]=1;//将k号结点纳入最短路
for(j=1;j<=N;j++)//对与k有关的结点进行更新
{
if(!s[j]&&use[j]&&dist[k]<inf&&c[k][j]<inf&&dist[j]>dist[k]+c[k][j])
dist[j]=dist[k]+c[k][j];
}
}
return dist[1];
}
void solove()
{
int i,j,m,an,t;an=inf;
for(i=0;i<=N;i++)
{
m=degree[i];dmax=m;dmin=m-M;//枚举最大等级,确实等级范围
for(j=0;j<=N;j++)
{
if(In(degree[j])) use[j]=1;
else use[j]=0;
}
t=dij();
if(an>t) an=t;//记录下最优值
}
cout<<an<<endl;
}
int main()
{
int i,j,k,m,n;
while(cin>>M>>N)
{
for(i=0;i<=N;i++) for(j=0;j<=N;j++) c[i][j]=inf;
for(i=1;i<=N;i++)
{
cin>>c[0][i];
cin>>degree[i]>>k;
for(j=1;j<=k;j++)
{
cin>>m>>n;
c[m][i]=n;
}
}
degree[0]=degree[1];
dmax=dmin=degree[0];
solove();
}
return 0;
}