Dijkstra(单源最短路径)-PKU1062

ACM算法日常

发布于 2018-08-07 19:45:11

7270

发布于 2018-08-07 19:45:11

文章被收录于专栏：ACM算法日常ACM算法日常

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;
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-01-08，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法