pku1062 昂贵的聘礼 (最短路Dijkstra)

题目:

题目是中文的大意就不用说了，从复杂的题目描述来看，要借助画图来更好地理解题意。画出图后发现其实就是一个最短路问题。用Dij解决，自己写了个以猷长为起点的Dij，无限WA，无奈到网上找了篇解题报告。发现向图中添加一个铺助起始点，可以很完美地解决问题。另外这题中加入了结点等级的限制，我们可以枚举最高等级，依据最高等级，确定能纳入最短路的结点的等级范围。至此，就完完全全的就是一个最短路了。关于Dijkstra算法，太经典了，就不多说了。实际上就是两步：1,将当前未纳入最短路的符合要求的距离最短结点纳入最短路;2,将所有与当前纳入的结点有关联并且未被纳入最短路的结点最短距离进行更新。图论中另一个求最小生成树的的经典算法Prim算法与Dij过程极其类似，都是贪心思想。只是一个是对顶点的选择，另外一个是对边的选择。

my code:

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